LeetCode 142 環形鏈表 II：快慢指針找環入口的數學證明與實現

題目大意

給定鏈表，返回環的入口節點；無環返回 null。進階：O(1) 空間。

解法一：哈希集合（簡單直觀，O(n) 空間）

ListNode* detectCycle(ListNode* head) {
    unordered_set seen;
    while (head) {
        if (seen.count(head)) return head;
        seen.insert(head);
        head = head->next;
    }
    return nullptr;
}

解法二：Floyd 快慢指針（O(1) 空間，經典必會）

階段 1：判斷有無環

slow 每次 1 步，fast 每次 2 步。若相遇，有環；若 fast 到達末尾，無環。

階段 2：找環入口（數學證明）

設：
- 頭節點到環入口距離 = a
- 環入口到相遇點距離 = b
- 環長度 = L
相遇時：slow 走 a+b，fast 走 a+b+kL（k 為繞環圈數）。
因 fast = 2×slow → 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;  // 無環
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;  // 入口節點
}

複雜度

• 時間：O(n)（階段 1 ≤ n 步，階段 2 ≤ a 步）。
• 空間：O(1)。

避坑指南

1. fast 移動前必須檢查 fast && fast->next，防止空指針解引用。
2. 無環時及時返回 nullptr。
3. 相遇後 必須 將一指針重置為 head，而非保持原位。

舉一反三

• LeetCode 141 環形鏈表：只需判斷有無環，階段 1 即可。
• 環長度計算：相遇後一指針原地，另一繞環計數直到再次相遇。
• 兩鏈表相交：同理雙指針對齊長度。