---
title: "206. Reverse Linked List"
url: "https://laigary.com/interview/coding/206-reverse-linked-list"
type: "note"
section: "coding"
date: "2024-03-12"
updated: "2026-07-26"
tags: ["Linked List", "Classic"]
---

# 206. Reverse Linked List

[206\. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/)

把一條單向鏈結串列整條反轉。

## 思路

在當前的節點中，我們要把原先指向下一個節點的方向，轉變為指向上一個節點（已經反轉完成的節點），接著處理下一個節點。

每一步要做四件事，順序不能亂：

1. 因為指向下一個節點的方向換掉後，會造成這個連結斷掉，所以要先透過一個暫存的節點紀錄下一個節點。
2. 此時可以把指向下一個節點的方向，指向上一個節點。
3. 該節點會變成下一個節點要指向的方向，所以要更新。
4. 轉換完畢，前往下一個節點。

**第 1 步是整題的關鍵**：`curr.next = prev` 這一行會立刻蓋掉 `curr` 原本的下一顆，所以**必須先存起來**，否則後面就找不到路了。「改指標之前先存下要用的東西」是所有鏈結串列題的通則 —— [143. Reorder List](/interview/coding/143-reorder-list)、[24. Swap Nodes in Pairs](/interview/coding/24-swap-nodes-in-pairs) 都是同一個道理。

**為什麼回傳 `prev` 而不是 `curr`？** 迴圈結束時 `curr` 已經走出串列變成 `None`，而 `prev` 停在最後一顆被處理的節點 —— 那正是反轉後的新頭。

這題本身很簡單，但**它是一整批題目的原語**：只要有人要你「反轉某一段」「兩兩交換」「判斷回文」，底層都是這三個指針的滾動。所以要練到閉著眼睛都能寫。

## 解題方向

### 迭代（三個指針滾動）

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head
        
        prev = None
        curr = head

        while curr:
            tmp = curr.next
            curr.next = prev
            prev = curr
            curr = tmp
        
        return prev
```

`prev` 初始是 `None` 不是隨便一個節點 —— 因為原本的頭在反轉後會變成尾，它的 `next` 就該是 `None`。這個初始值同時也把「空串列」的情況處理掉了。

### 遞迴

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        if head is None or head.next is None:
            return head
        
        last = self.reverseList(head.next)

        # Pointing next's next to self. 
        head.next.next = head
        head.next = None

        return last
```

遞迴版的想法是「**先讓後面整段反轉好，我再把自己接到尾巴**」：

- `last` 是反轉後的新頭，它會**原封不動地一路往上回傳** —— 每一層都回傳同一個節點
- `head.next.next = head` 是把「原本的下一顆」的 `next` 指回自己。因為後面已經反轉完，`head.next` 現在是那一段的**尾巴**，所以接上去剛好
- `head.next = None` 不能省，否則自己和下一顆會互相指、形成環

**注意 `head.next` 在這裡有兩個身分**：遞迴前它是「下一顆」，遞迴後那一段已經反轉，它變成「反轉段的尾巴」。想清楚這件事這段就通了。

**遞迴版的深度等於節點數。** Python 預設的 `sys.setrecursionlimit` 是 1000，所以本機跑 n = 5000 會直接 `RecursionError`（判題環境通常會調高，這裡指的是預設值）。迭代版沒有這個顧慮。

## 補充

**這題是這些題的原語**：

- [92. Reverse Linked List II](/interview/coding/92-reverse-linked-list-ii) —— 只反轉 `left` 到 `right` 這一段。它的解法就是在本題上疊兩層：先做「反轉前 n 個」，再做「先走到 left」
- [143. Reorder List](/interview/coding/143-reorder-list) —— 找中點後反轉後半段，再交錯合併
- [234. Palindrome Linked List](/interview/coding/234-palindrome-linked-list) —— 反轉後半段再和前半比對，就能 $O(1)$ 空間判斷回文
- [24. Swap Nodes in Pairs](/interview/coding/24-swap-nodes-in-pairs) —— 每兩顆反轉一次

骨架整理見 [Linked List 模板](/interview/coding/linked-list-template)。

## 複雜度

**迭代**
- 時間 $O(n)$ — 每個節點只被走過一次
- 空間 $O(1)$ — 只有三個指針

**遞迴**
- 時間 $O(n)$ — 每個節點一次
- 空間 $O(n)$ — 遞迴堆疊，深度等於節點數

其中 `n` 是節點數。兩者時間相同，**迭代版空間 $O(1)$ 而且不會爆堆疊**，是面試的預設答案。