單鏈表反轉三大算法圖解：從暴力破解到原地指針操作的極致優雅

問題：如何反轉單鏈表？

給定單鏈表 head → 1 → 2 → 3 → NULL，反轉為 head → 3 → 2 → 1 → NULL。三種經典思路：

1. 陣列法：存入陣列，逆序重建。空間 O(N)，非原地。
2. 三指標迭代法：原地修改指向，空間 O(1)，最經典。
3. 頭插法：將第 2~N 個節點依次插入頭節點後，最後移動頭節點。空間 O(1)，思路獨特。

方法一：陣列法（教學用，生產環境不推薦）

遍歷鏈表存入 Node* arr[N]，再按 arr[N-1] → arr[N-2] → ... → arr[0] 重鏈。缺點：額外 O(N) 空間，兩次遍歷，破壞原結構局部性。

方法二：三指標迭代法（標準答案）

使用 p（已反轉部分尾部）、q（待處理節點）、r（剩餘鏈表）三指標協作：

Node* ReverseList(Node* head) {
    if (!head || !head->next) return head;
    Node *p = head, *q = head->next, *r;
    head->next = nullptr; // 原頭節點變尾，next 置空

    while (q) {
        r = q->next;   // 1. 保存剩餘鏈表
        q->next = p;   // 2. 反轉指向
        p = q;         // 3. p 前進
        q = r;         // 4. q 前進
    }
    return p; // p 為新頭節點
}

圖解關鍵步驟：

1. 初始：p→1、q→2、1→NULL
2. 第 1 輪：r→3、q→2→1、p→2、q→3
3. 第 2 輪：r→NULL、q→3→2→1、p→3、q→NULL
4. 循環結束，返回 p (3)

方法三：頭插法（巧妙利用頭節點）

思路：保持 head 不動，將第 2 個節點開始的每個節點，依次「摘下」插入到 head 之後。最終 head 後面是逆序鏈表，最後將 head 移至新表尾。

Node* ReverseList3(Node* head) {
    if (!head || !head->next) return head;
    Node *p = head->next, *q;
    while (p->next) {
        q = p->next;       // 待插入節點
        p->next = q->next; // p 跳過 q
        q->next = head->next; // q 插入 head 後
        head->next = q;
    }
    // 最後處理 head：成環 → 斷環 → 移動 head
    p->next = head;
    head = p->next->next;
    p->next->next = nullptr;
    return head;
}

圖解精髓：

1. 初始：head→1→2→3→NULL
2. 插入 2：head→2→1→3→NULL
3. 插入 3：head→3→2→1→NULL
4. 成環斷環調整 head，完成。

完整可執行程式碼（含建立、顯示、反轉）

#include <iostream>
using namespace std;

struct Node { int val; Node* next; };

Node* Create() { /* 互動式建立鏈表 */ }
void Display(Node* head) { /* 遍歷輸出 */ }
Node* ReverseList2(Node* head) { /* 三指標法 */ }
Node* ReverseList3(Node* head) { /* 頭插法 */ }

int main() {
    Display(ReverseList3(Create()));
    return 0;
}

總結對比

掌握三指標迭代法是核心，理解頭插法能拓寬思維，兩者都是單鏈表指針操作功力的試金石。