LeetCode 141 環形鏈表：快慢指針檢測環

問題描述

給定鏈表頭節點，判斷鏈表中是否有環。若存在環，快慢指針最終會相遇。

核心算法：Floyd 快慢指針 (龜兔賽跑)

• 慢指針 slow 每次走 1 步。
• 快指針 fast 每次走 2 步。
• 若有環，快指針終將在環內追上慢指針（相對速度 1 步/輪）。
• 若無環，快指針先到達 nullptr。

關鍵代碼 (C++)

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

關鍵點

• 初始化：slow=fast=head 或 head->next 均可，邏輯一致。
• 循環條件：fast && fast->next 確保 fast->next->next 安全。
• 相遇判斷：在移動**後**判斷 slow == fast。

進階：找到環入口 (LeetCode 142)

相遇後，將一指針重置為 head，兩指針同速 (1步/輪) 前進，再次相遇點即為環入口。證明基於路程關係：a = c + (n-1)(b+c)。

複雜度分析

• 時間：O(n) — 無環時 fast 走完；有環時 slow 進環後最多繞環一圈相遇。
• 空間：O(1) — 僅兩指針。

總結

LeetCode 141 是快慢指針檢測環的教科書級例題。此模板廣泛適用於「鏈表環檢測、數字序列循環檢測 (如快樂數)、函數圖找環」等問題。掌握「相遇後找入口」延伸技巧可解決 LeetCode 142。