Linked List · 03 / 05

Reverse Linked List反轉串列

迭代三指標與遞迴兩種寫法。

用在：指標操作的基本功、面試高頻

時間複雜度O(n)

空間複雜度O(1)

難度入門

前置知識Singly Linked List、Recursion

01為什麼需要它

面試最常出現的串列題

Reverse Linked List 幾乎是每家公司的暖身題，再往上是反轉區間、每 k 個一組反轉、判斷回文串列。它們全部建立在同一個三指標動作上。

為什麼用它反轉串列是「指標操作」最純粹的練習：每個節點只做一件事（把箭頭轉向），但順序錯了整條就斷。練到不用想就寫對，之後的串列題都是這個動作的變形。

把數字串列相加、判斷回文

兩個用串列表示的大數要相加（個位數在最後），或判斷一個串列讀正讀反都一樣。串列只能往前走，沒辦法從尾巴倒著看。

為什麼用它把後半段反轉，就能從兩端同時往中間走。這是「用 O(1) 空間處理需要倒著看的問題」的標準手法，比複製成陣列省記憶體。

理解遞迴版與迭代版的取捨

同一件事，迭代版三個指標搞定，遞迴版四行但要 O(n) 的呼叫堆疊。串列一長遞迴就爆。

為什麼用它這是最適合對照兩種寫法的題目。迭代版是實務上該用的，遞迴版是「相信更小的自己」那個思考方式的最佳範例。

看到這些關鍵字就想到它：反轉、倒著看、從尾巴開始、回文串列、k 個一組、區間反轉、prev / cur / next 三指標。

02核心概念

反轉一條串列，就是把每個節點的 next 箭頭轉向：原本指向後面，改成指向前面。難的地方只有一個：一旦把 cur.next 改掉，就找不到後面的路了。所以每一步都要先把下一個存起來，再改指標。

迭代版用三個指標。prev 是「已經反轉好的那段」的頭，一開始是 None；cur 是正在處理的節點；nxt 暫存後面的路。每一輪四個動作：存 nxt、轉箭頭、prev 前進、cur 前進。迴圈結束時 cur 是 None，prev 停在原本的最後一個節點，它就是新 head。O(n) 時間，O(1) 額外空間。

遞迴版換一種思考：相信 reverse(head.next) 會把後面那段反轉好、回傳新 head。那自己只要做一件事：原本的下一個節點現在是那段的尾巴，把它的 next 指回自己，再把自己的 next 設成 None。程式碼更短，但呼叫堆疊 O(n)，串列很長時會 stack overflow。

反轉區間是常見的變形。用頭插法：固定區間第一個節點 cur 不動，反覆把 cur 後面那個節點「拔出來、插到區間最前面」，做 right − left 次。搭配 dummy 節點，left = 1 也不用特判。

03演算法步驟

1prev = None、cur = head。
2迴圈條件 while cur。進入後先 nxt = cur.next，保住後面的路。
3cur.next = prev，箭頭轉向。這是唯一真正改變結構的一行。
4prev = cur、cur = nxt，兩個指標一起往前一格。順序不能反，否則 cur 會追不到原本的下一個。
5迴圈結束回傳 prev。用空串列、單節點、兩節點各跑一次確認邊界。

04互動示範

逐步執行迭代版。看每一輪四個動作怎麼把一個節點的箭頭轉向：綠色是已經反轉好的部分，prev 永遠停在它的頭。

1 → 2 → 3 → 4

None

1→

cur

2→

3→

4∅

箭頭是每個節點的 next：→ 指向右邊、← 指向左邊、∅ 指向 None。綠色代表箭頭已經轉向。

1def reverse(head):
2    prev, cur = None, head
3    while cur:
4        nxt = cur.next
5        cur.next = prev
6        prev = cur
7        cur = nxt
8    return prev

步驟 0/17prev 指向 None，cur 指向 head。prev 是「已經反轉好的那段」的頭，一開始是空的。

05程式碼

迭代版、遞迴版、以及用頭插法反轉區間。三個都建議手寫一次，遞迴版特別注意 head.next.next = head 那一行在做什麼。

# 迭代：三個指標，每個節點把箭頭轉向。O(n) 時間、O(1) 空間
def reverse(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next          # 1. 先記住後面的路
        cur.next = prev         # 2. 箭頭轉向
        prev = cur              # 3. 兩個指標往前推
        cur = nxt
    return prev                 # prev 停在原本的最後一個節點


# 遞迴：相信 reverse(head.next) 會把後面反轉好並回傳新 head，
# 自己只要把「原本的下一個」的 next 指回自己。O(n) 空間（呼叫堆疊）
def reverse_rec(head):
    if head is None or head.next is None:
        return head
    new_head = reverse_rec(head.next)
    head.next.next = head       # 後面那個節點現在是尾巴，把它接回我
    head.next = None            # 我變成新的尾巴
    return new_head


# 反轉區間 [left, right]（LeetCode 92）：頭插法
def reverse_between(head, left, right):
    dummy = ListNode(0, head)
    before = dummy
    for _ in range(left - 1):
        before = before.next    # before 停在區間前一個
    cur = before.next           # cur 固定不動，每次把它後面那個搬到區間最前面
    for _ in range(right - left):
        moved = cur.next
        cur.next = moved.next
        moved.next = before.next
        before.next = moved
    return dummy.next

06練習題

LeetCode 206Reverse Linked ListEasy
LeetCode 234Palindrome Linked List（找中點 + 反轉後半）Easy
LeetCode 92Reverse Linked List II（區間反轉）Medium
LeetCode 24Swap Nodes in PairsMedium
LeetCode 25Reverse Nodes in k-GroupHard

上一篇Doubly Linked List 下一篇Fast & Slow Pointers