---
title: "92. Reverse Linked List II"
url: "https://laigary.com/interview/coding/92-reverse-linked-list-ii"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-26"
tags: ["Linked List", "Classic"]
---

# 92. Reverse Linked List II

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

只反轉第 `left` 到第 `right` 個節點（1-indexed），其餘保持原樣。

這一題的難度是中等，可是實作上的細節非常多。迭代可以完成這個任務，可是真的很多邊角情況要處理；用遞迴的方式好處理很多，不過比較不好理解。

## 思路

### 從 206 疊上來的三層階梯

這題最好的理解方式是把它拆成三層，每一層只比上一層多做一件事：

| 層 | 做什麼 | 比上一層多了什麼 |
|---|---|---|
| [206. `reverseList(head)`](/interview/coding/206-reverse-linked-list) | 反轉**整條** | — |
| `reverseN(head, n)` | 反轉**前 n 個** | 反轉完要接回**繼任者**（第 n+1 顆） |
| `reverseBetween(head, left, right)` | 反轉 **left..right** | 先**走到 left** 再動手 |

**先把中間那層寫出來，最後一層就只是包一下。** 反過來直接想 `left..right` 會被兩端的邊界卡死。

### 中間那層要多做什麼

反轉部分 Linked List 有幾點要完成：

1. 我們要返回的是第 `n` 個點，`n` 從 `1` 開始算。
2. 一開始的起頭點，要指向剩下的節點的開頭，這裡用**繼任者（successor）**來稱呼。

```text
# 原先的節點
[1] -> [2] -> [3] -> [4] -> [5]

# 我們要完成的目標
[1] <- [2] <- [3]    [4] -> [5]
 |                    ^
 |                    |
 ----------------------
```

圖裡那條從 `[1]` 拉到 `[4]` 的線就是「接回繼任者」—— 這是 206 沒有的一步。206 反轉完，原本的頭直接指 `None`；這裡它必須指向沒被反轉的那一段。

### 遞迴怎麼走

處理的方式跟 [206](/interview/coding/206-reverse-linked-list) 很像，都是先處理 base case，這裡多了一個 base case 要處理：

- **`n == 1`**：已經成功遞迴到目標處。此時回傳 `head.next, head` —— 分別是**繼任者**與**當前節點**（它會成為反轉段的新頭）。
- **走到串列末端**：沒有繼任者，回傳 `None, head`。

接著就是一層一層地返回，每一層回傳的都是**（繼任者，反轉段的新頭）**。回到某一層時做三件事：

1. 目前當前節點還是指向原先指向的節點
2. 將當前節點原先指向的節點，指向當前節點（`head.next.next = head`）
3. 當前節點指向**繼任者**（`head.next = successor`）

第 3 點是和 206 唯一的差別 —— 206 那裡寫的是 `head.next = None`。

**「繼任者」和「新頭」為什麼都要回傳？** 因為它們的傳遞方式不同：新頭（`last`）在整個遞迴過程中**原封不動地往上傳**，繼任者則是**每一層都要拿來接**。用一個 tuple 一起帶上去最省事。

## 解題方向

### 第一步：反轉前 n 個

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseN(self, head: ListNode, n: int) -> ListNode:
        if n == 1:
            successor = head.next
            return successor, head
        if not head or not head.next: 
            return None, head
        successor, last = self.reverseN(head.next, n - 1)
        head.next.next = head
        head.next = successor
        return successor, last
```

### 第二步：遞迴走到 left

接下來題目的邏輯就很簡單了。題目問的不是從 `1 -> n`，而是從 `left -> right`，所以我們就一步一步的遞迴走過去，一直到 `left` 為 `1` 的時候，就是上面那個函式的情況：

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

    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if left == 1:
            successor, last = self.reverseN(head, right)
            return last
        
        head.next = self.reverseBetween(head.next, left - 1, right - 1)
        return head
            
    
    def reverseN(self, head, n):
        if n == 1:
            successor = head.next
            return successor, head

        if not head or not head.next:
            return None, head

        successor, last = self.reverseN(head.next, n - 1)
        head.next.next = head
        head.next = successor
        return successor, last
```

**`left` 和 `right` 要一起減。** 往下走一格之後，原本的「第 `left` 個」在子問題裡變成「第 `left - 1` 個」，`right` 同理 —— 兩個都是相對於當前 `head` 的位置。只減 `left` 是最常見的錯誤。

`head.next = self.reverseBetween(...)` 這行是在說「後面那段處理完之後，把結果接回我的 `next`」—— 因為反轉可能會換掉那一段的頭。

### 迭代版

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

    def reverseN(self, head, n):
        if head is None or head.next is None:
            return head
        pre, cur, nxt = None, head, head.next
        while n > 0:
            cur.next = pre
            pre = cur
            cur = nxt
            if nxt is not None:
                nxt = nxt.next
            n -= 1
        head.next = cur
        return pre


    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if left == 1:
            return self.reverseN(head, right)
        pre = head
        for i in range(1, left - 1):
            pre = pre.next
        pre.next = self.reverseN(pre.next, right - left + 1)
        return head
```

同樣是三層階梯，只是「走到 left」從遞迴換成 `for` 迴圈、「反轉 n 個」從遞迴換成 206 那組滾動指針。

`head.next = cur` 是迭代版的「接回繼任者」—— 迴圈跑完 `cur` 剛好停在第 `n+1` 顆，而 `head` 是反轉段的**尾巴**（它原本是頭）。

`right - left + 1` 是要反轉的節點**個數**，不是索引 —— 這個 +1 很容易漏。

## 補充

**還有一種一趟完成的迭代寫法叫「穿針引線」**：用一個 dummy node 固定在 `left - 1` 的位置，然後把 `left..right` 之間的節點一顆一顆「摘下來、插到最前面」，不需要輔助函式也不用先反轉再接回。我沒有用這個角度寫過，但知道它存在 —— 面試官如果要求「一趟、不用額外函式」，那就是它。

**用 dummy head 可以省掉 `left == 1` 的特例。** 在真正的頭前面掛一顆假節點，`left` 就永遠有「前一顆」，兩個分支合而為一。這是鏈結串列題的通用技巧，見 [21. Merge Two Sorted Lists](/interview/coding/21-merge-two-sorted-lists)。

**同一組工具的題目**：[206. Reverse Linked List](/interview/coding/206-reverse-linked-list)（本題的原語）、[143. Reorder List](/interview/coding/143-reorder-list)（反轉後半段）、[234. Palindrome Linked List](/interview/coding/234-palindrome-linked-list)（反轉後半段再比對）、[24. Swap Nodes in Pairs](/interview/coding/24-swap-nodes-in-pairs)（每兩顆反轉）。整理見 [Linked List 模板](/interview/coding/linked-list-template)。

## 複雜度

**遞迴**
- 時間 $O(n)$ — 走到 `left` 花 $O(left)$，反轉花 $O(right - left)$，合計不超過一趟
- 空間 $O(n)$ — 遞迴堆疊；最壞情況（`right = n`）深度等於節點數

**迭代**
- 時間 $O(n)$ — 同上，一趟走完
- 空間 $O(1)$ — 只有幾個指針

其中 `n` 是節點數。

兩者時間相同，**迭代版空間 $O(1)$，而且不受遞迴深度限制**。