C 語言實現無頭結點單鏈表逆序打印：頭插法構建新鏈表

無頭結點單鏈表逆序打印：頭插法新鏈表法

單鏈表結構決定了只能從頭向後遍歷。要實現逆序輸出，經典思路是：遍歷原鏈表，將每個節點的數據取出，用頭插法構建一個新鏈表。新鏈表的順序天然就是原鏈表的逆序。無頭結點版本需額外處理空表、首節點等邊界情況。

核心數據結構

typedef struct Node {
    int element;
    struct Node *next;
} Node;

算法邏輯圖解

原鏈表: 1 -> 2 -> 3 -> NULL
遍歷取出: 1, 2, 3

頭插構建新鏈表:
插入 1: 新鏈表 = 1 -> NULL
插入 2: 新鏈表 = 2 -> 1 -> NULL
插入 3: 新鏈表 = 3 -> 2 -> 1 -> NULL
結果: 3 2 1 (原鏈表逆序)

完整代碼實現

#include 
#include 
#include 

typedef struct Node {
    int element;
    struct Node *next;
} Node;

// 尾插法創建 (測試用)
Node* TailInsertCreate(Node *head) {
    Node *pInsert, *pMove = head;
    pInsert = (Node*)malloc(sizeof(Node));
    pInsert->next = NULL;
    scanf("%d", &pInsert->element);
    if (pInsert->element <= 0) { free(pInsert); return NULL; }
    
    while (pInsert->element > 0) {
        if (!head) { head = pInsert; pMove = head; }
        else { pMove->next = pInsert; pMove = pInsert; }
        pInsert = (Node*)malloc(sizeof(Node));
        pInsert->next = NULL;
        scanf("%d", &pInsert->element);
    }
    free(pInsert);
    return head;
}

// 打印鏈表
void PrintList(Node *head) {
    while (head) { printf("%d ", head->element); head = head->next; }
    printf("\n");
}

// 全局逆序鏈表頭指針 (簡化傳參)
Node *g_reverseHead = NULL;

// 頭插法輔助函數
void HeadInsert(Node *pInsert) {
    if (!g_reverseHead) { g_reverseHead = pInsert; }
    else { pInsert->next = g_reverseHead; g_reverseHead = pInsert; }
}

// 核心：掃描原鏈表並頭插構建逆序鏈表
void ScanAndReverse(Node *head) {
    if (!head) { printf("原鏈表為空\n"); return; }
    
    Node *pMove = head;
    Node *pInsert;
    
    while (pMove) {
        pInsert = (Node*)malloc(sizeof(Node));
        memset(pInsert, 0, sizeof(Node));
        pInsert->element = pMove->element;
        pInsert->next = NULL;
        
        HeadInsert(pInsert); // 頭插到逆序鏈表
        
        pMove = pMove->next;
    }
    printf("逆序鏈表構建完成\n");
}

int main() {
    Node *list = NULL;
    printf("輸入數據 (>0 構建, <=0 結束): ");
    list = TailInsertCreate(list);
    
    printf("原序列: ");
    PrintList(list);
    
    ScanAndReverse(list);
    printf("逆序輸出: ");
    PrintList(g_reverseHead);
    
    // 內存清理 (略)
    return 0;
}

運行示例

輸入數據 (>0 構建, <=0 結束): 10 20 30 40 0
原序列: 10 20 30 40
逆序鏈表構建完成
逆序輸出: 40 30 20 10

關鍵點對比：無頭結點 vs 帶頭結點

空間優化：遞歸法 (慎用於長鏈表)

void ReversePrintRecursive(Node *head) {
    if (!head) return;
    ReversePrintRecursive(head->next);
    printf("%d ", head->element);
}
// 缺點: 棧深度 O(n)，長鏈表導致棧溢出

工程推薦：數組拷貝法 (最簡、緩存友好)

void ReversePrintArray(Node *head) {
    int len = 0;
    for (Node *p = head; p; p = p->next) len++;
    int *arr = malloc(len * sizeof(int));
    int i = 0;
    for (Node *p = head; p; p = p->next) arr[i++] = p->element;
    for (i = len - 1; i >= 0; i--) printf("%d ", arr[i]);
    printf("\n");
    free(arr);
}

總結

「頭插法構建新鏈表」是單鏈表逆序的標準教學解法，清晰展示了指針操作的「後進先出」特性。無頭結點版本雖邊界處理稍繁，但邏輯本質相同。實際工程中，數組拷貝法因無內存分配開銷、緩存局部性佳、代碼極簡，通常是首選。掌握多種方案，根據場景 (教學演示 vs 生產環境、嵌入式內存受限 vs 服務端高性能) 靈活選型。