LeetCode Linked List Cycle II 解題詳解：快慢指針找環入口

問題描述

給定單鏈表頭節點，判斷是否有環，若有返回環入口節點，否則返回 null。要求 O(1) 空間。

Floyd 判環算法（快慢指針）

1. 快指針 fast 每次走 2 步，慢指針 slow 每次走 1 步。若有環，必相遇。
2. 相遇後，將一指針移至頭節點，另一留在相遇點，兩指針同速（1步/次）前進，再次相遇點即為環入口。

數學證明

設頭節點到環入口距離 a，環入口到相遇點距離 b，環長度 L。相遇時：
slow 路程 = a + b
fast 路程 = a + b + kL = 2(a+b) ⇒ a + b = kL ⇒ a = kL - b。
即：從頭節點走 a 步到入口，從相遇點繼續走 a 步（即 kL - b）也到入口。

代碼實現

ListNode* detectCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }
    if (!fast || !fast->next) return nullptr; // 無環

    fast = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow; // 入口節點
}

邊界情況

• 空鏈表、單節點無環：直接返回 null。
• 單節點自環：head->next = head，算法正常工作。
• 環入口即頭節點：相遇後第二階段立即相遇於頭節點。

複雜度

• 時間 O(n)：第一階段 ≤ n 步相遇，第二階段 ≤ a 步。
• 空間 O(1)：僅兩指針。