Leetcode 142.环形链表II（画图分析）
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。
解题思路：
我们使用两个指针，fast 与 slow。它们起始都位于链表的头部。
随后，slow 指针每次向后移动一个位置，而 fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。
如下图所示，设链表中环外部分的长度为 a。slow 指针进入环后，又走了 b 的距离与 fast 相遇。此时，fast 指针已经走完了环的 n 圈，因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc。
根据题意，任意时刻，fast 指针走过的距离都为 slow 指针的 2 倍。因此，我们有
a+(n+1)b+nc=2(a+b) ⟹ a=c+(n−1)(b+c) 的等量关系，我们会发现：从相遇点到入环点的距离加上 n−1圈的环长，恰好等于从链表头部到入环点的距离。
因此，当发现 slow 与 fast 相遇时，我们再slow的指针指向链表头部；随后，它和 fast每次向后移动一个位置。最终，它们会在入环点相遇。
1.为什么slow指针走不到一圈就可以和fast指针相遇呢？
我们先假设没有环外部分，整个链表就是一个环，slow和fast从环中同一点出发，fast的速度是slow的两倍。当slow绕环一圈，回到起点时，fast刚好跑完两圈，两者相遇。
当存在环外部分时，slow到达入环点时，fast指针已进入环内，相当于提前追赶了一段时间，将提前达到【相差一个格子】的状态，再次相遇时，slow还没有绕环一圈。因为即使fast不“提前追赶”，相遇时slow也才刚好绕环一圈而已。
因此，无论是否有环外部分，两指针相遇时，slow都不可能绕环超过一圈。
这里补充一句，相遇时，fast是可能绕环多圈的，很多文章的观点是错误的，在此纠正一下。
2.为什么fast和slow一定会相遇？
我们知道，两人绕操场跑圈，只要一直跑，快的肯定会追上慢的，即再次相遇。
但本题场景略有不同，我们可以把操场想成一个个格子组成的链表环，slow每次跳一格，fast每次跳两格，只有两人站在同一个格子上，才算相遇。
在此要求下，还能保证一定相遇吗，答案是肯定的。
我们来看slow和fast之间的距离，有以下几种情况：
- 相距1格，下次相遇。
- 相距2步，下一次移动，变为相距1格。
- 其它时刻，每次环内移动，距离缩短1，直至相距2格。
通过分析可知，快慢指针一定会相遇。
代码实现：
java
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) {
return head;
}
// 初始化两个指针：快指针和慢指针
ListNode fast = head;
ListNode slow = head;
boolean isCycle = false;
// 寻找环的存在
while (fast != null && fast.next != null) {
// 快指针每次移动两步
fast = fast.next.next;
// 慢指针每次移动一步
slow = slow.next;
// 如果快指针追上了慢指针，说明存在环
if (fast == slow) {
isCycle = true;
break;
}
}
// 重新将慢指针指向头节点，快指针保持在相遇点
slow = head;
// 寻找环的起始节点
while (isCycle && fast != slow) {
// 快指针和慢指针同时每次移动一步
fast = fast.next;
slow = slow.next;
}
// 如果存在环，则返回环的起始节点；否则返回null
return isCycle ? slow : null;
}
}
python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def detectCycle(self, head):
# 如果头节点为空，直接返回
if head is None:
return head
# 初始化快慢指针
fast = head
slow = head
isCycle = False
# 检查链表中是否存在环
while fast and fast.next:
# 快指针每次移动两步
fast = fast.next.next
# 慢指针每次移动一步
slow = slow.next
# 如果快慢指针相遇，说明存在环
if fast == slow:
isCycle = True
break
# 如果检测到环，慢指针回到起点，快指针留在相遇点
if isCycle:
slow = head
# 快慢指针同时移动一步，直到找到环的起始点
while fast != slow:
fast = fast.next
slow = slow.next
return slow
else:
return None
c++
#include <iostream>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
// 如果头节点为空，直接返回
if (head == nullptr) {
return head;
}
// 初始化快慢指针
ListNode *fast = head;
ListNode *slow = head;
bool isCycle = false;
// 检查链表中是否存在环
while (fast != nullptr && fast->next != nullptr) {
// 快指针每次移动两步
fast = fast->next->next;
// 慢指针每次移动一步
slow = slow->next;
// 如果快慢指针相遇，说明存在环
if (fast == slow) {
isCycle = true;
break;
}
}
// 如果检测到环，慢指针回到起点，快指针留在相遇点
if (isCycle) {
slow = head;
// 快慢指针同时移动一步，直到找到环的起始点
while (fast != slow) {
fast = fast->next;
slow = slow->next;
}
return slow;
} else {
return nullptr;
}
}
};
时间复杂度分析：
- 第一阶段（检测环的存在）：两个指针 fast 和 slow 在链表中移动，fast 每次移动两步，slow 每次移动一步。如果存在环，两个指针最终会相遇。由于 fast 指针比 slow 指针速度快一倍，因此最多遍历链表中的所有节点一次。因此，第一阶段的时间复杂度为 O(n)，其中
n是链表中节点的总数。 - 第二阶段（寻找环的起始点）：一旦检测到环，将 slow 指针重新置于链表头，fast 指针从相遇点开始。两指针再次以相同的速度前进，直到找到环的起始点。由于两指针每次都移动一步，因此最多需要遍历链表中的节点一次，时间复杂度同样为 O(n)。
总的时间复杂度为：O(n)。
空间复杂度分析：
该算法仅使用了两个额外的指针 fast 和 slow 来遍历链表，除此之外没有使用额外的空间。因此，空间复杂度为 O(1)。
评论区