LeetCode 141 環形鏈表：快慢指針法完整解析

題目回顧

給定單向鏈表頭節點 `head`，判斷鏈表中是否有環。無法修改鏈表，空間複雜度最好 O(1)。

思路演進

嘗試 1：記錄訪問節點（哈希集合）

時間 O(N)，空間 O(N)。面試常被要求優化空間。

嘗試 2：從頭遍歷比較（暴力）

對第 k 個節點，檢查前 k-1 個是否相同。時間 O(N²)，N=5000 會 TLE。

正解：Floyd 判圈算法（快慢指針）

**核心洞見**：若有環，快指針（每次 2 步）終將追上慢指針（每次 1 步），如同操場跑道雙人跑。

標準實作

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head || !head->next) return false;
        
        ListNode *slow = head;
        ListNode *fast = head->next; // 或 head，邏輯微調
        
        while (fast && fast->next) {
            if (slow == fast) return true; // 相遇 → 有環
            slow = slow->next;
            fast = fast->next->next;
        }
        return false; // fast 走到 null → 無環
    }
};

關鍵細節

數學證明（直觀版）

• 設環前長度 a，環長 b。慢指針入環時，快指針已在環內走過 a 步，兩者距離為 a % b。
• 每輪快指針比慢指針多走 1 步，距離每輪減 1。
• 最多 b 輪追上，總步數 ≤ a + b = O(N)。

延伸：找環入口（LeetCode 142）

相遇後，將一指針重置為 head，兩指針同速（1 步）前進，再次相遇點即為環入口。證明：相遇時慢指針走 a + x，快指針走 2(a+x) = a + x + kb → a = kb - x。從 head 走 a 步到入口，從相遇點走 kb - x 步也到入口。

心得與技巧

• **反向思考**：不從頭找環，而是想「兩人跑步何時相遇」。
• **畫圖演練**：紙上畫鏈表、標註指針移動，極大降低心智負載。
• **邊界測試**：單節點自環、兩節點環、大環、無環。
• **通用模板**：快慢指針適用於「找中點」、「判斷回文鏈表」、「LC 876 中間節點」等。

總結

快慢指針是鏈表環問題的「核武級」武器：O(1) 空間、O(N) 時間、代碼極簡。掌握其核心邏輯與邊界處理，同類問題迎刃而解。