92. Reverse Linked List II

──────────────────────────────────────────────────────────────────────

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

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

思路

從 206 疊上來的三層階梯

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

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

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

中間那層要多做什麼

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

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

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

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

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

遞迴怎麼走

處理的方式跟 206 很像，都是先處理 base case，這裡多了一個 base case 要處理：

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

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

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

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

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

解題方向

第一步：反轉前 n 個

# 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 的時候，就是上面那個函式的情況：

# 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」—— 因為反轉可能會換掉那一段的頭。

迭代版

# 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。

同一組工具的題目：206. Reverse Linked List（本題的原語）、143. Reorder List（反轉後半段）、234. Palindrome Linked List（反轉後半段再比對）、24. Swap Nodes in Pairs（每兩顆反轉）。整理見 Linked List 模板。

複雜度

遞迴

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

迭代

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

其中 n 是節點數。

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