C語言實現單鏈表逆序打印：頭插法構建新鏈表法詳解

單鏈表僅有 next 指針，無法直接從尾向前遍歷。本文實現一種經典思路：遍歷原鏈表，以頭插法構建新鏈表，新鏈表自然呈逆序，最後打印新鏈表並釋放內存。該算法 O(n) 時間、O(n) 空間，邏輯清晰易懂。

核心算法步驟

1. 使用尾插法構建原鏈表（保持輸入順序）。
2. 聲明新鏈表頭指針 pReverseList = NULL。
3. 遍歷原鏈表，對每個節點：
     ① 分配新節點複製數據
     ② 頭插法插入新鏈表
     ③ 推進原鏈表游標
4. 打印新鏈表（即逆序輸出）。
5. 釋放新鏈表內存（原鏈表保持不變）。

關鍵代碼實現

Node* pReverseList = NULL;  // 全局或靜態變量，保存逆序鏈表頭

// 頭插法輔助函數
void HeadInsert(Node* pInsert) {
    if (!pReverseList) {
        pReverseList = pInsert;        // 首節點
    } else {
        pInsert->next = pReverseList;  // 新節點指向原首節點
        pReverseList = pInsert;        // 更新頭指針
    }
}

// 掃描原鏈表並構建逆序鏈表
void ScanAndReverse(Node* pHead) {
    if (!pHead) {
        printf("%s: 原鏈表為空\n", __FUNCTION__);
        return;
    }
    
    Node* pMove = pHead;
    Node* pInsert = NULL;
    
    while (pMove) {
        // 分配新節點複製數據（不修改原鏈表）
        pInsert = (Node*)malloc(sizeof(Node));
        if (!pInsert) break;
        pInsert->element = pMove->element;
        pInsert->next = NULL;
        
        HeadInsert(pInsert);  // 頭插入逆序鏈表
        pMove = pMove->next;
    }
    printf("%s: 逆序鏈表構建完成\n", __FUNCTION__);
}

// 打印並釋放逆序鏈表
void PrintAndFreeReverse() {
    Node* p = pReverseList;
    while (p) {
        printf("%d ", p->element);
        Node* tmp = p;
        p = p->next;
        free(tmp);
    }
    pReverseList = NULL;
    printf("\n");
}

頭插法逆序原理圖解

原鏈表:  1 -> 2 -> 3 -> 4 -> NULL

頭插過程:
插入1:  逆序表 = 1
插入2:  2 -> 1
插入3:  3 -> 2 -> 1
插入4:  4 -> 3 -> 2 -> 1

結果:  4 3 2 1  (逆序)

完整測試主函數

int main() {
    Node* list = CreateList();  // 尾插法建表，輸入：10 20 30 40 -1
    PrintList(list);            // 10 20 30 40
    
    ScanAndReverse(list);       // 構建逆序鏈表
    PrintAndFreeReverse();      // 40 30 20 10
    
    PrintList(list);            // 原鏈表不變：10 20 30 40
    FreeList(list);
    return 0;
}

對比：其他逆序打印方案

頭插法構建新鏈表是單鏈表逆序打印的教科書級方案，完美詮釋了「頭插法天然逆序」的指針邏輯。掌握此模式，對理解鏈表反轉、棧的鏈式實現、圖算法邊表構建均有遷移價值。