cbangchen
11/11/2018 - 7:34 AM

142. Linked List Cycle II- Medium - 2018.7.30

/* 
同样设置快慢指针,步进分别为 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;
    }
};