Programming Skills: Linked List Cycle 2

[題目]

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

https://leetcode.com/problems/linked-list-cycle-ii/description/

給你一個link list head，請問有沒有cycle，cycle的起點是哪個node?

[思路]

之前那題只問你有沒有cycle，我們用雙跑者是否相遇來判定是否有cycle。

今天這題還問你cycle的起點是甚麼，這就困難了，因為雙跑者相遇之處可不一定是cycle起點。

但雙跑者所提供的資訊不只有相遇點，還有相遇所花的步數。

(這故事告訴我們你要充分利用所有資訊)

假設左邊是list起點，X是cycle起點，M是相遇的點，a,b,c是各段長度。

當雙跑者p1&p2，初次相會在M時，所跑的長度分別是

p1: a+b

p2: a+k*(b+c)+b , k是整數

而且因為p1,p2速差為兩倍(前一題教過這技巧)，因此可得到一個等式

2*(a+b) = a+k*(b+c)+b

a+b = k*(b+c)

a = (k-1)*(b+c) + c

然後我們可以巧妙的運用上述紅色的等式來解題。

此等式告訴我們，"a" 等於 "k-1個圈加上c"，因此如果我們布置兩個等速跑者p3,p4

p3從起點跑，p4從M點跑，他們將會相會在X，也就是cycle的開頭。


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:

    ListNode* CycleMeetpoint(ListNode *head) {//return meet point
        ListNode *p1=head, *p2=head;
        while(p2 && p2->next){
            p2=p2->next->next;
            p1=p1->next;
            if(p2==p1)
                return p1;
        }
        return NULL;
    }    
    
    ListNode *detectCycle(ListNode *head) {
        ListNode* m = CycleMeetpoint(head);
        if(m==NULL) return NULL;
        ListNode* p3=m;
        ListNode* p4=head;
        while(p3!=p4){
            p3=p3->next;
            p4=p4->next;
        }
        return p3;
    }
};