206. Reverse Linked List

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

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

思路

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

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

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

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

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

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

解題方向

迭代（三個指針滾動）

# 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。這個初始值同時也把「空串列」的情況處理掉了。

遞迴

# 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 —— 只反轉 left 到 right 這一段。它的解法就是在本題上疊兩層：先做「反轉前 n 個」，再做「先走到 left」
143. Reorder List —— 找中點後反轉後半段，再交錯合併
234. Palindrome Linked List —— 反轉後半段再和前半比對，就能 $O (1)$ 空間判斷回文
24. Swap Nodes in Pairs —— 每兩顆反轉一次

骨架整理見 Linked List 模板。

複雜度

迭代

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

遞迴

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

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