Reverse Linked List

題目描述

給定一個 Linked List 的 head，反轉整個 Linked List，回傳新的 head。

輸入: [1,2,3,4,5]
輸出: [5,4,3,2,1]

輸入: [1,2]
輸出: [2,1]

解題思路

初始化

設 prev = null 作為反轉後的尾端、curr = head 作為當前處理節點

保存下一個

先執行 next = curr.next 保存原本的下一個節點，否則改 curr.next 後就斷鏈了

反轉指針

執行 curr.next = prev 讓當前節點指向前一個節點，完成這個節點的反轉

前進

prev = curr 把前指針推進、curr = next 把當前指針推進到下一個待處理節點

重複直到結束

當 curr 為 null 時所有節點已反轉，prev 指向原尾端即新的 head

程式碼

C#

csharp

public class Solution {
    // 迭代解法
    public ListNode ReverseList(ListNode head) {
        ListNode prev = null;
        var curr = head;
 
        while (curr != null) {
            var next = curr.next; // 先保存下一個
            curr.next = prev;    // 反轉指針
            prev = curr;         // prev 前進
            curr = next;         // curr 前進
        }
        return prev; // prev 是新的 head
    }
 
    // 遞迴解法
    public ListNode ReverseListRecursive(ListNode head) {
        if (head == null || head.next == null) return head;
        var newHead = ReverseListRecursive(head.next);
        head.next.next = head; // 讓下一個節點指向自己
        head.next = null;     // 斷開原本的指向
        return newHead;
    }
}

TypeScript

typescript

// 迭代解法
function reverseList(head: ListNode | null): ListNode | null {
    let prev: ListNode | null = null;
    let curr = head;
 
    while (curr) {
        const next = curr.next; // 先保存下一個
        curr.next = prev;      // 反轉指針
        prev = curr;           // prev 前進
        curr = next;           // curr 前進
    }
    return prev;
}
 
// 遞迴解法
function reverseListRecursive(head: ListNode | null): ListNode | null {
    if (!head || !head.next) return head;
    const newHead = reverseListRecursive(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

Python

python

# 迭代解法
def reverseList(head: Optional[ListNode]) -> Optional[ListNode]:
    prev = None
    curr = head
 
    while curr:
        next_node = curr.next  # 先保存下一個
        curr.next = prev       # 反轉指針
        prev = curr            # prev 前進
        curr = next_node       # curr 前進
    return prev
 
# 遞迴解法
def reverseListRecursive(head: Optional[ListNode]) -> Optional[ListNode]:
    if not head or not head.next:
        return head
    new_head = reverseListRecursive(head.next)
    head.next.next = head  # 讓下一個節點指向自己
    head.next = None       # 斷開原本的指向
    return new_head

複雜度分析

| | Time | Space | |--|------|-------| | 迭代 | O(n) | O(1) | | 遞迴 | O(n) | O(n) call stack |

迭代 Time O(n) 是因為 curr 從 head 走到 null 恰好 n 步，每步做常數操作。Space O(1) 是因為只用 prev、curr、next 三個變數。遞迴 Space O(n) 是因為遞迴深度等於鏈表長度，每層呼叫佔用一個 stack frame。

邊界情況

空鏈表：head 為 null，迭代直接回傳 null（不進入迴圈），遞迴在 base case 回傳
單一節點：[1] 不需要反轉，兩種解法都直接回傳 head
兩個節點：[1,2] 只需一步反轉 — 迭代跑一輪迴圈、遞迴只遞迴一次

圖解

prev=null, curr=1→2→3

反轉 1→

null←1, curr=2→3

反轉 2→

null←1←2, curr=3

反轉 3→

null←1←2←3, curr=null

return prev→

新 head = 3→2→1→null

圖表展示了迭代反轉 [1,2,3] 的三步過程：每步把 curr 的 next 指向 prev，然後推進指針。當 curr 變成 null 時 prev 指向 3，就是新的 head，形成 3→2→1→null。

進階觀點

💡面試追問

Q: 迭代和遞迴各自的優缺點是什麼？ A: 迭代 O(1) 空間、沒有 stack overflow 風險，但需要手動管理三個指針。遞迴更直觀（信任子問題已解決），但 O(n) call stack 空間，鏈表極長時可能溢位。面試中兩種都要能寫。

Q: 遞迴解法中 head.next.next = head 為什麼不會造成環？ A: 因為緊接著的 head.next = null 斷開了原本的正向連結。這兩行必須搭配：先建立反向連結，再斷開正向連結。如果只做第一步不做第二步，最末兩個節點會形成環。

Reverse Linked List 是超高頻基礎題，許多進階題都以它為子步驟：LC 92 Reverse Linked List II（部分反轉）、LC 25 Reverse Nodes in k-Group、LC 234 Palindrome Linked List。

理解測驗

🤔 迭代解法中，為什麼要先執行 next = curr.next？

🤔 遞迴解法中 head.next.next = head 這行在做什麼？