LeetCode 141 環形鏈表：O(1) 空間快慢指針法詳解

LeetCode 141 環形鏈表：O(1) 空間快慢指針法詳解

題目：給定單鏈表頭節點，判斷是否有環。進階要求：不使用額外空間（即 O(1) 空間複雜度）。

快慢指針（Floyd 判圈算法）

定義兩個指針 slow、fast 初始指向頭節點。slow 每次移動 1 步，fast 每次移動 2 步。若有環，二者必相遇；若 fast 遇到 null 則無環。

Python 實現

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        return False

為什麼能相遇？

設環長 L，快慢指針進環後相對速度為 1 步/輪。快指針每輪比慢指針多走 1 步，最多 L 輪追上。時間複雜度 O(N)，空間 O(1)。

常見變體

• LeetCode 142：找環入口節點 → 相遇後，一指針回頭，另一留原地，同速前進，再次相遇點即入口
• LeetCode 160：相交鏈表 → 同理，雙指針遍歷兩條鏈表