题目描述：
给出一个链表head，长度为 $ n $ ，如果存在环，找到环的第一个节点（环的入口）；否则返回null。不允许修改链表。
数据范围：
$ 0\le n\le 10^4 $
题解：
使用快慢指针，一个速度为 $ 2 $ ，一个速度为 $ 1 $ ，遍历链表，相遇时证明链表有环。相遇之后将快指针移到链表头，然后继续同时遍历，相遇时就是链表的环入口。
证明：
假设快指针速度为 $ 2v $ ，满指针速度 $ v $ ，则可以得到：
消去 $ vt $ 可以得到：
所以可以得到：
因此可以看出 $ a $ 的长度等于 $ c $ 加若干圈。因此重新将快指针移动到head，再次同时遍历会刚好在环的入口处相遇。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution
{
public:
ListNode *detectCycle(ListNode *head)
{
if (head == nullptr || head->next == nullptr)
return nullptr;
ListNode *fast = head, *slow = head;
while (true)
{
fast = fast->next;
if (fast == nullptr)
return nullptr;
fast = fast->next;
if (fast == nullptr)
return nullptr;
slow = slow->next;
if(slow == fast) break;
}
fast = head;
while (fast != slow)
{
fast = fast->next;
slow = slow->next;
}
return fast;
}
};
|