C 語言單向鏈表就地反轉：圖解與代碼逐行講解

問題代碼

Linklist *reverse(Linklist *head) { // 假設帶頭結點
    Linklist *p, *t;
    p = head->next;      // p 指向第一個資料結點
    t = p->next;         // t 指向第二個結點
    p->next = NULL;      // 斷開第一個結點，使其成為新鏈表尾部
    while (t != NULL) {
        p = t->next;     // 暫存 t 的下一個
        t->next = head->next; // 將 t 插入頭結點之後 (頭插法)
        head->next = t;
        t = p;           // 移動 t 到下一個待處理結點
    }
    return head;
}

核心算法：頭插法重建鏈表

此演算法將原鏈表視為兩部分：

• 已反轉部分：`head->next` 為頭的新鏈表，初始只有第一個結點 (p)，其 `next=NULL`。
• 待處理部分：`t` 及其後續結點。

每次迴圈從待處理部分取出第一個結點 `t`，插入到已反轉部分的頭部（即 `head->next` 之後），實現就地反轉。

圖解演變過程

原始:  HEAD -> 1 -> 2 -> 3 -> 4 -> NULL
       p=1, t=2
步驟1: p->next=NULL  =>  HEAD -> 1 -> NULL   (t=2->3->4)
步驟2: 取 t=2, 插入頭部 => HEAD -> 2 -> 1 -> NULL  (t=3->4)
步驟3: 取 t=3, 插入頭部 => HEAD -> 3 -> 2 -> 1 -> NULL (t=4)
步驟4: 取 t=4, 插入頭部 => HEAD -> 4 -> 3 -> 2 -> 1 -> NULL (t=NULL)
結束: 返回 HEAD，新鏈表 4->3->2->1

關鍵問題解答：`p = t->next` vs `t->next = head->next`

本質區別：前者是「向後看」保存未來；後者是「向前連」接入過去。兩者指向完全不同的記憶體位置。

無頭結點版本（更通用）

Node* reverse(Node* head) {
    Node *prev = NULL, *curr = head, *next = NULL;
    while (curr) {
        next = curr->next; // 1. 暫存
        curr->next = prev; // 2. 反轉指針
        prev = curr;       // 3. 移動 prev
        curr = next;       // 4. 移動 curr
    }
    return prev; // 新頭結點
}

此版本雙指針 `prev`/`curr` 更直觀，無需虛擬頭結點，適用於所有單向鏈表反轉場景。

複雜度分析

• 時間：O(n) —— 單次遍歷。
• 空間：O(1) —— 僅使用常數額外指針。