LeetCode 刷題日記
EP.08

Linked List
Pointer 操作的思維方式

#206 Reverse · #21 Merge · #141 Cycle — Linked List 三大核心題

Joseph Chen
2024
Back to Blog
5 min read
1.2k views

Linked List 題目讓很多人頭痛，不是因為邏輯複雜，而是因為同時在腦海中追蹤多個 pointer 的位置很容易搞亂。這篇用圖示化的方式，把 Reverse、Merge、Cycle 三個核心題的 pointer 操作說清楚。

Linked List 的結構

Linked List 的每個節點（Node）包含兩樣東西：值（val）和指向下一個節點的 pointer（next）。

1
→
2
→
3
→
4
None
Python 的 ListNode 定義
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 建立 1 → 2 → 3 → None
node3 = ListNode(3)
node2 = ListNode(2, node3)
node1 = ListNode(1, node2)
head = node1
⚠️ LeetCode 的 Linked List 題目，Node 的定義是固定的，你只需要操作 head（第一個 node 的 pointer）。操作 Linked List 的核心：改變 .next 的指向，而不是移動資料本身。

#206 Reverse Linked List

把 1 → 2 → 3 → 4 → None 變成 4 → 3 → 2 → 1 → None。

需要三個 pointer：prev（前一個）、curr（當前）、next_node（暫存下一個，避免斷鏈）。

指針移動過程（1→2→3→None）：

初始
prev=Nonecurr=1
從 head 開始
第1輪
prev=1curr=2
1.next = None，curr 往前
第2輪
prev=2curr=3
2.next = 1，curr 往前
第3輪
prev=3curr=None
3.next = 2，curr = None 停止
#206 Reverse Linked List — Iterative
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head

        while curr:
            next_node = curr.next   # 1. 先存好下一個，避免斷鏈
            curr.next = prev        # 2. 反轉 pointer
            prev = curr             # 3. prev 往前
            curr = next_node        # 4. curr 往前

        return prev   # curr 變 None 時，prev 就是新的 head
⏱ Time: O(n)💾 Space: O(1)

也可以用遞迴解，但 iterative 版本的空間複雜度是 O(1)，是面試首選。

Dummy Node：讓邊界情況消失的技巧

Linked List 操作最麻煩的是邊界情況：head 是 None 怎麼辦？要插入第一個節點怎麼辦？Dummy Node 是一個虛擬的前置節點，讓你不用對 head 做特殊處理。

Dummy Node 概念
# 沒有 Dummy Node：需要特別處理 head 是 None 的情況
if head is None:
    head = new_node
else:
    # ... 一般邏輯

# 有 Dummy Node：統一處理，不需要特判
dummy = ListNode(0)
dummy.next = head
curr = dummy
# ... 一般邏輯（所有 insert 都是 curr.next = ...）
return dummy.next   # 跳過 dummy，回傳真正的 head

#21 Merge Two Sorted Lists

把兩個排序好的 Linked List 合併成一個排序好的 Linked List。

Input / Output
list1: 1 → 2 → 4 → None
list2: 1 → 3 → 4 → None

output: 1 → 1 → 2 → 3 → 4 → 4 → None

用 Dummy Node + 兩個 pointer 同時遍歷，每次選較小的接上去：

#21 Merge Two Sorted Lists
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(0)   # Dummy Node 避免處理 head
        curr = dummy

        while l1 and l2:
            if l1.val <= l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next

        # 把剩下的直接接上（不用再逐一比較）
        curr.next = l1 if l1 else l2

        return dummy.next
⏱ Time: O(n + m)💾 Space: O(1)

#141 Linked List Cycle：快慢指針

判斷 Linked List 有沒有環（某個節點的 next 指向前面的節點）。

最聰明的解法是 Floyd's Cycle Detection（龜兔賽跑算法）：一個慢指針每次走一步，一個快指針每次走兩步。如果有環，快指針一定會追上慢指針；如果沒有環，快指針會先到 None。

有環的情況（1 → 2 → 3 → 4 → 2 loop）：

初始🐢 slow=1🐇 fast=1
第1步🐢 slow=2🐇 fast=3
第2步🐢 slow=3🐇 fast=2 (loop)
第3步🐢 slow=4🐇 fast=4 ← 相遇！→ 有環
#141 Linked List Cycle — Floyd's Algorithm
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next          # 走一步
            fast = fast.next.next     # 走兩步

            if slow == fast:          # 相遇 → 有環
                return True

        return False   # fast 到 None → 無環
⏱ Time: O(n)💾 Space: O(1)

為什麼快指針一定能追上慢指針？

進入環之後，每一輪快指針比慢指針多走一步。如果環長度是 k，最多 k 輪之內，快指針就會追上慢指針。

Linked List 的四個核心技巧

🔄

Pointer 反轉

Reverse Linked List

操作前先存好 next_node，避免斷鏈。三個 pointer：prev、curr、next_node。

👻

Dummy Node

Merge Two Lists、Remove Nth Node

在 head 前放虛擬節點，統一邊界處理，最後回傳 dummy.next。

🐢🐇

Fast & Slow Pointer

Linked List Cycle、Find Middle

快指針走兩步、慢指針走一步，用來找環、找中點、找倒數第 k 個。

📏

固定間距雙指針

Remove Nth Node From End

兩個指針保持固定距離，快指針先走 k 步，再同時移動。

Linked List 題目的訣竅：在紙上把節點畫出來，一步一步追蹤 pointer 的位置。寫程式前先確認每一步的狀態，操作前先存好 next，否則一斷鏈就找不回來了。

本篇重點整理

🔗Linked List 操作 = 改變 .next 的指向，不是移動資料
💾操作前先 next_node = curr.next，防止斷鏈找不回來
👻Dummy Node 消滅邊界特判，幾乎所有 insert/remove 都用得到
🐢🐇Floyd 快慢指針：有環就會相遇，O(1) 空間解決 Cycle 偵測

上一篇

EP.07 — Binary Search

每次砍掉一半，O(log n) 的魔法

下一篇

EP.09 — Tree & DFS/BFS

即將推出

LeetCode
Linked List
Two Pointers
Python
EP.08