LeetCode Linked List Cycle：快慢指針判環

問題描述

判斷單鏈表是否有環。要求 O(1) 空間。

快慢指針法

慢指針每次走 1 步，快指針每次走 2 步。若有環，快指針必定在環內追上慢指針（相對速度 1 步/輪）。若無環，快指針先到達末尾 nullptr。

完整代碼

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head) return false;
        ListNode *slow = head, *fast = head->next;
        while (slow && fast && fast->next) {
            if (slow == fast) return true;
            slow = slow->next;
            fast = fast->next->next;
        }
        return false;
    }
};

關鍵點

• 初始化 fast = head->next 避免單節點自環誤判
• 循環條件檢查 fast && fast->next 防止空指針解引用
• 時間 O(n)，空間 O(1)
• 數學證明：設環長 L，入環前長度 a，相遇點距入環口 b。慢針走 a+b，快針走 a+b+kL。速度比 1:2 → a+b = kL，必相遇

擴展：找環入口

見下一題（Linked List Cycle II）。相遇後，一指針回頭，另一留原地，同速前進，再次相遇處即為入口。

快慢指針是鏈表環問題的「瑞士軍刀」，掌握其相遇數學原理可靈活解決變種題。