题目链接:https://leetcode.cn/problems/linked-list-cycle-ii/
思路如下:
用两个指针 fast, slow 同时从起点开始走,fast 每次走两步,slow 每次走一步。
如果过程中 fast 走到 null,则说明不存在环。否则当 fast 和 slow 相遇后,让 slow 回到起点,fast 待在原地不动,然后两个指针每次分别走一步,当再次相遇时,相遇点就是环的入口。
证明:
如上图所示,
a
a
a 是起点,
b
b
b 是环的入口,
c
c
c 是两个指针的第一次相遇点,
∣
a
b
∣
|ab|
∣ab∣ 之间的距离是
x
x
x,
∣
b
c
∣
|bc|
∣bc∣ 之间的距离是
y
y
y,
∣
c
b
∣
|cb|
∣cb∣ 之间的距离是
z
z
z。
由 LeetCode 141. 环形链表 可知,第一次相遇时,slow 指针在环上走不到一圈,即 slow 所走的距离是
x
+
y
x+y
x+y,fast 所走的距离是
x
+
(
y
+
z
)
∗
n
+
y
x+(y+z)∗n+y
x+(y+z)∗n+y。
因为 fast 走过的距离是 slow 的两倍,所以有
x
+
(
y
+
z
)
∗
n
+
y
=
2
(
x
+
y
)
x+(y+z)∗n+y=2(x+y)
x+(y+z)∗n+y=2(x+y),即
x
=
(
n
−
1
)
∗
(
y
+
z
)
+
z
x=(n−1)*(y+z)+z
x=(n−1)∗(y+z)+z。
那么我们让 fast 从
c
c
c 点开始走,走
x
x
x 步,会恰好走到
b
b
b 点;让 slow 从
a
a
a 点开始走,走
x
x
x 步,也会走到
b
b
b 点。
C++ 代码如下:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
auto fast = head, slow = head;
while (true) {
if (fast == NULL || fast->next == NULL) return NULL;
fast = fast->next->next;
slow = slow->next;
if (fast == slow) break;
}
slow = head;
while (fast != slow) {
fast = fast->next;
slow = slow->next;
}
return fast;
}
};