---
title: "141. Linked List Cycle"
url: "https://laigary.com/interview/coding/141-linked-list-cycle"
type: "note"
section: "coding"
date: "2023-11-01"
updated: "2026-07-26"
tags: ["Linked List", "Two Pointers", "Hash Table"]
---

# 141. Linked List Cycle

[141\. Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/)

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

## 思路

### 直覺解：記住走過的節點

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

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

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

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

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

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

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

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

## 解題方向

### Hash Set

```python
# 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
```

### 快慢指針

```python
# 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` 出發，把相遇判斷移到迴圈裡：

```python
        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](/interview/coding/142-linked-list-cycle-ii)：相遇之後把其中一個指針放回 `head`，兩個都改成一次走一步，再次相遇的地方就是環的入口。那個結論需要一點數學推導，但寫起來只多三行。

**快慢指針的其他用途**：[876. Middle of the Linked List](/interview/coding/876-middle-of-the-linked-list)（快的走完，慢的剛好在中點）、[143. Reorder List](/interview/coding/143-reorder-list)、[19. Remove Nth Node From End of List](/interview/coding/19-remove-nth-node-from-end-of-list)（讓快的先走 n 步）。整理見 [Linked List 模板](/interview/coding/linked-list-template)。

## 複雜度

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

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

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