LeetCode 142 Linked List Cycle II 詳解

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

核心算法：Floyd 快慢指針 + 數學推導

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

數學證明

設：頭到入口距離 a，入口到相遇點距離 b，環長 c。
相遇時：slow 走 a+b，fast 走 2(a+b) = a+b + k·c（k 為繞環圈數）。
⇒ a+b = k·c ⇒ a = k·c - b = (k-1)·c + (c-b)。
c-b 為相遇點到入口距離。故從頭出發走 a 步，與從相遇點走 a 步（繞 k-1 圈 + c-b）同步到達入口。

參考代碼 (C++ / Python / Java)

// C++
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 *ptr = head;
                while (ptr != slow) {
                    ptr = ptr->next;
                    slow = slow->next;
                }
                return ptr;
            }
        }
        return nullptr;
    }
};

# Python
class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                ptr = head
                while ptr != slow:
                    ptr = ptr.next
                    slow = slow.next
                return ptr
        return None

// Java
class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

關鍵細節

• 空鏈表/單節點：循環條件 fast && fast->next 自然處理。
• 無環：fast 先到達 null，返回 nullptr。
• 環入口即頭節點：a=0，相遇點即入口，第二階段 ptr=head, slow=meet 直接相等，返回頭節點。
• 不修改鏈表：僅讀取指針，滿足 O(1) 空間。

複雜度分析

面試延伸

• 環長度：相遇後一指針不動，另一繞環計數直到再次相遇。
• 哈希集合法：O(n) 空間，遍歷記錄訪問節點，首次重複即入口（簡單但不滿足 O(1) 空間）。
• 單鏈表相交節點 (LeetCode 160)：雙指針換頭法，同樣利用路徑長度差。

總結

LeetCode 142 是「快慢指針」的經典進階應用。它將「環檢測」與「入口定位」融為一體，數學推導嚴謹優雅。掌握 a = (k-1)c + (c-b) 這一核心等式，可靈活解決鏈表環相關所有變體問題。面試中能清晰講出證明並寫出無 Bug 代碼，是指標操作基本功的重要體現。