LeetCode 142. Linked List Cycle II [Medium] [C++] 解題筆記

 這題是 141. Linked List Cycle 的進階題，除了要判斷 linked list 中是否含有 cycle 之外還必須找出 cycle 的起點。

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

想法:

    這題要利用 Floyd cycle detection algorithm 來做，定快慢兩個指標，快指標每次走訪兩個 nodes，慢指標每次走訪

一個，當兩個指標相遇的時候表示存在 cycle，這時將慢指標移回原點，而快指標留在原地，然後兩者就當前位置繼續走訪但快指標降低

速度變成一次也只走訪一個 node，當兩個指標再次相遇時該 node 即為 cycle 的入口。

簡略證明: 假設進入 cycle 前的 node 長度為 x ，cycle 長度為 l ，快慢指標第一次相遇的 node 距離 cycle 入口 d (cycle 的第 d 個 node)

慢指針在第一次相遇時走得距離為 s = x + d。

，則因為快指針速度為慢指針的兩倍，因此兩者第一次相遇時慢指針走了 s ，快指針走了 x + nl(繞cycle至少一圈才能追上) + d

=> 2s = x + nl + d => 2*(x + d) = x + nl + d => 2x + 2d = x + nl + d => d + x = nl

=> x = nl - d。

於是可以得到結論: 從起點走到 cycle 入口的距離會等於從第一次相遇的 node 走回到 cycle 入口的距離 (或是繞 cycle 幾圈之後再到入口的距離)。

完整程式碼:

/* O(n) time, O(1) space 
 * Folyd's cycle detection algorithm
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {
                break;
            }
        }
        if (fast == nullptr || fast->next == nullptr) { return nullptr; }
        slow = head;
        while (fast != slow) {
            slow = slow->next;
            fast = fast->next;
        }
        return fast;
    }
};