LeetCode 單鏈表反轉：遞歸與迭代雙重解法詳解

題目描述

給定單鏈表頭節點 head，將鏈表反轉並返回新頭節點。

示例：1 → 2 → 3 → 4 → 5 反轉為 5 → 4 → 3 → 2 → 1

解法一：遞歸法（自頂向下）

核心思想：假設 head->next 之後的部分鏈表已反轉完成，返回新頭節點 newHead。此時 head->next 指向原第二個節點（現尾節點），只需將其 next 指向 head，並斷開 head->next，即完成整表反轉。

struct ListNode* reverseList(struct ListNode* head) {
    // 基線條件：空表或單節點
    if (head == NULL || head->next == NULL) return head;

    // 遞歸反轉子表
    struct ListNode* newHead = reverseList(head->next);

    // 關鍵步驟：將原下一節點指向當前節點
    head->next->next = head;
    // 斷開原向後指針，防止循環
    head->next = NULL;

    return newHead;
}

遞歸過程圖解

原表：1 → 2 → 3 → 4 → 5 → NULL
                        ↓ 遞歸到尾部
反轉後：5 → 4 → 3 → 2 → 1 → NULL
        ↑              ↑
      newHead        原 head 變為尾節點

解法二：迭代法（三指針，O(1) 空間）

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *prev = NULL, *curr = head, *next = NULL;
    while (curr) {
        next = curr->next;  // 暫存下一節點
        curr->next = prev;  // 反轉指針
        prev = curr;        // 前移 prev
        curr = next;        // 前移 curr
    }
    return prev;  // prev 為新頭節點
}

複雜度對比

進階：部分反轉（LeetCode 92）

若需反轉第 m 到 n 位置的節點，可結合「虛擬頭節點」+「定位前驅」+「區間反轉」技巧，同樣採用迭代或遞歸實現。

總結

• 面試首推迭代法：空間優、無棧溢出風險、易於擴展
• 遞歸法適合理解指針反轉本質，代碼極簡
• 核心操作均為 curr->next = prev，本質是逐個反轉 next 指針方向