原题链接
本题要求找到环的入口，且
O
(
n
)
O(n)
O(n)的时间复杂度，
O
(
1
)
O(1)
O(1)的空间复杂度。
参考了很是充分证明的题解，很多疑惑得到了解决
-
先判断是否有环：快慢指针fast，slow，直到两者第二次相遇的时候那么判断确定有环。（第一次是在起点）
-
考虑如何找到入口，设
h
e
a
d
head
head到链表环入口的结点数是
a
a
a，环的结点数是
b
b
b
f
=
2
s
=
s
+
n
b
f=2s=s+nb
f=2s=s+nb，表示在
f
f
f和
s
s
s再次相遇时，
f
f
f比
s
s
s多走了
n
n
n次环。
f
=
2
n
b
,
s
=
n
b
f=2nb,s=nb
f=2nb,s=nb
那么所有到达链表入口的点都为
a
+
k
b
(
k
≥
0
)
a+kb(k\geq0)
a+kb(k≥0)
考虑我们现在位置一为
o
n
e
one
one，从起点
h
e
a
d
head
head开始，位置二
t
w
o
two
two为
s
s
s与
f
f
f相遇的那个结点。
，那么初始情况下
o
n
e
=
0
one=0
one=0，
t
w
o
=
n
b
two=nb
two=nb
所以当
o
n
e
one
one和
t
w
o
two
two都跑了
a
a
a步，
o
n
e
=
a
,
t
w
o
=
n
b
+
a
one=a,two=nb+a
one=a,two=nb+a，均符合入口为
a
+
k
b
a+kb
a+kb的要求，即
o
n
e
=
a
+
0
∗
b
(
k
=
0
)
,
t
w
o
=
a
+
n
∗
b
(
k
=
n
,
n
≥
0
)
one=a+0*b(k=0),two=a+n*b(k=n,n\geq0)
one=a+0∗b(k=0),two=a+n∗b(k=n,n≥0)，此时
o
n
e
one
one和
t
w
o
two
two都到达了入口
所以最后操作就是：
先快慢指针找到第一次相遇点，然后第二次分别从相遇点和起点开始直到相遇。
/**
* 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) {
ListNode* fast = head, *slow = head;
while(fast != nullptr) {
if(fast->next == nullptr || fast->next->next == nullptr) return nullptr;
fast = fast->next->next;
slow = slow->next;
if(slow == fast) break;
}
ListNode* one = head, *second = slow;
while(one != second) {
one = one->next;
second = second->next;
}
return one;
}
};
