LeetCode 141: Linked List Cycle - 快慢指針 O(1) 空間檢測環

題目

給定單鏈表頭節點，判斷鏈表中是否存在環。進階：不使用額外空間（O(1) 空間複雜度）。

Floyd 判圈算法（快慢指針）

• slow 每次走 1 步，fast 每次走 2 步。
• 若有環，快指針終會在環內追上慢指針（相遇）。
• 若無環，fast 先到達 nullptr。

代碼實現

/**
 * Definition for singly-linked list.
 * struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head || !head->next) 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;
    }
};

證明直觀理解

環長 L，快慢指針進環後相對速度 1 步/輪，至多 L 輪相遇。時間 O(n)，空間 O(1)。

延伸：找環入口 (LeetCode 142)

相遇後，將一指針重置為 head，兩指針同速前進，再次相遇點即為環入口。