/*
同样设置快慢指针,步进分别为 1,2
起始点为 X,循环起点为 Y,第一次相遇的点为 Z
起点到循环的起点之间距离为 xy,循环的起点到第一次相遇的点距离为 yz,循环的长度为 r
有关系为:xy + yz = nr,n 为大于 0 的整数
xy + yz = nr
=> xy + yz = (n - 1)r + (r - yz) + yz
=> xy = (n - 1)r + (r - yz)
由 xy = (n - 1)r + (r - yz) 这一关系,可以推出 => 步进同样为 1 的指针,分别从起始点 X 和第一次相遇的 Z 点出发,最后都会相遇 Y 点。
*/
class Solution {
public:
ListNode *detectCycle( ListNode *head ) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
ListNode *slow2 = head;
while (slow2 != slow) {
slow2 = slow2->next;
slow = slow->next;
}
return slow2;
}
}
return NULL;
}
};