141. Linked List Cycle

──────────────────────────────────────────────────────────────────────

判斷一條鏈結串列裡有沒有環。

思路

直覺解：記住走過的節點

「有沒有環」等於「會不會走到同一個節點兩次」。所以最直接的做法就是邊走邊把節點丟進 set，下次遇到已經在 set 裡的就是環。

要注意記的是節點本身（記憶體位址）而不是節點的值 —— 值可以重複，[1, 1, 1] 沒有環但值都一樣。Python 的物件預設用 id 做 hash，所以 seen.add(head) 正是我們要的語意。

這個解法一定寫得出來，缺點是 $O (n)$ 空間。

進階解：快慢指針（Floyd 判圈法）

要把空間降到 $O (1)$ ，關鍵洞見是：

如果有環，跑得快的最終一定會從後面追上跑得慢的。

想成兩個人在操場跑步。沒有環的話跑道有終點，快的先衝出去、結束；有環的話跑道是圓的，快的每一步比慢的多走一格，兩者的差距每輪縮小 1，所以一定會在某個時刻剛好重疊 —— 不會「跳過」，因為差距是一格一格減少的。

這個「差距每輪減 1，所以必定相遇」是要能講出來的部分，只說「快的會追上慢的」不夠有說服力。

解題方向

Hash Set

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:

        seen = set()

        while head:
            if head in seen:
                return True
            seen.add(head)
            head = head.next

        return False

快慢指針

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if head is None:
            return False
        slow = head
        fast = head.next

        while slow != fast:
            if fast is None or fast.next is None:
                return False
            slow = slow.next
            fast = fast.next.next
        return True

這個版本讓 fast 從 head.next 出發，刻意讓兩者一開始就錯開一格，這樣才能用 while slow != fast 當迴圈條件 —— 如果兩個都從 head 出發，第一輪就相等，迴圈直接不進去。

另一種更常見的寫法是兩個都從 head 出發，把相遇判斷移到迴圈裡：

        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

兩種都對，選一種寫熟就好。差別只在「起點錯開、條件在外」還是「起點相同、判斷在內」—— 混著寫最容易出錯。

fast is None or fast.next is None 這個檢查不能少：沒有環的話 fast 會先走到底，少了它就會 AttributeError。

補充

找出環的入口是 142. Linked List Cycle II：相遇之後把其中一個指針放回 head，兩個都改成一次走一步，再次相遇的地方就是環的入口。那個結論需要一點數學推導，但寫起來只多三行。

快慢指針的其他用途：876. Middle of the Linked List（快的走完，慢的剛好在中點）、143. Reorder List、19. Remove Nth Node From End of List（讓快的先走 n 步）。整理見 Linked List 模板。

複雜度

Hash Set

時間 $O (n)$ — 每個節點最多走一次
空間 $O (n)$ — 最壞情況整條串列都進了 set

快慢指針

時間 $O (n)$ — 沒有環時快指針 $n / 2$ 步走到底；有環時慢指針最多繞環一圈就會被追上
空間 $O (1)$ — 只有兩個指針

其中 n 是節點數。兩者時間同級，快慢指針的價值完全在空間 —— 面試被問「能不能不用額外空間」，要的就是它。