C 語言單鏈表構建：頭插法與尾插法完整實現 (無頭結點版)

編輯：關於C語言

單鏈表構建的兩大基石：頭插法與尾插法

單鏈表的構建本質是「重複插入節點」。頭插法在頭結點後插入，新節點始終為首節點，輸出順序與輸入順序相反；尾插法在尾部插入，保持輸入順序。無頭結點版本需額外處理空表時的頭指針賦值。本文提供完整、可編譯的雙版本實現。

數據結構定義

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

初始化與打印 (通用)

void initList(Node **head) { *head = NULL; }

void printList(Node *head) {
    if (!head) { printf("鏈表為空\n"); return; }
    while (head) { printf("%d ", head->element); head = head->next; }
    printf("\n");
}

頭插法 `HeadInsert`：逆序構建

Node* HeadInsert(Node *head) {
    Node *pInsert = (Node*)malloc(sizeof(Node));
    if (!pInsert) return NULL;
    pInsert->next = NULL;
    scanf("%d", &pInsert->element);
    if (pInsert->element <= 0) { free(pInsert); return NULL; }
    
    while (pInsert->element > 0) {
        if (!head) { head = pInsert; }
        else {
            pInsert->next = head; // 關鍵：新節點指向原頭
            head = pInsert;       // 關鍵：頭指針前移
        }
        pInsert = (Node*)malloc(sizeof(Node));
        if (!pInsert) return head;
        pInsert->next = NULL;
        scanf("%d", &pInsert->element);
    }
    free(pInsert);
    return head;
}

尾插法 `TailInsert`：順序構建

Node* TailInsert(Node *head) {
    Node *pInsert, *pMove = head;
    pInsert = (Node*)malloc(sizeof(Node));
    if (!pInsert) return NULL;
    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 {
            // 遍歷到尾部 (無尾指針版本，O(n²) 總複雜度)
            while (pMove->next) pMove = pMove->next;
            pMove->next = pInsert;
        }
        pInsert = (Node*)malloc(sizeof(Node));
        if (!pInsert) return head;
        pInsert->next = NULL;
        scanf("%d", &pInsert->element);
    }
    free(pInsert);
    return head;
}

優化尾插法：維護尾指針 O(n)

Node* TailInsertOptimized(Node *head) {
    Node *pInsert, *tail = NULL;
    // ... 輸入邏輯同前 ...
    while (pInsert->element > 0) {
        if (!head) { head = tail = pInsert; }
        else { tail->next = pInsert; tail = pInsert; } // O(1) 尾插
        // ... 分配下一節點 ...
    }
    return head;
}

對比總結表

維度	頭插法	尾插法 (無尾指針)	尾插法 (有尾指針)
輸入/輸出順序	相反	一致	一致
空表處理	head = pInsert	head = pMove = pInsert	head = tail = pInsert
核心鏈接	pInsert->next = head; head = pInsert;	遍歷找尾 → pMove->next = pInsert	tail->next = pInsert; tail = pInsert;
總時間複雜度	O(n)	O(n²)	O(n)
適用場景	棧、逆序需求、哈希桶	教學演示	隊列、順序存儲、文件讀取

主函數測試

int main() {
    Node *list;
    initList(&list);
    
    printf("頭插法輸入 (1 2 3 0): ");
    list = HeadInsert(list);
    printList(list); // 輸出: 3 2 1
    
    // 重置
    Node *p;
    for (p = list; p; ) { Node *t=p; p=p->next; free(t); }
    initList(&list);
    
    printf("尾插法輸入 (1 2 3 0): ");
    list = TailInsertOptimized(list);
    printList(list); // 輸出: 1 2 3
    
    return 0;
}

關鍵避坑指南

malloc 失敗檢查：每次分配後必須判空，否則解引用導致崩潰。
最後多分配節點釋放：循環結束時已分配下一節點但未使用，必須 free(pInsert)。
指針操作順序：頭插法「先連後移」(pInsert->next=head; head=pInsert;)；尾插法「先連後移尾指針」。順序錯誤導致鏈表斷裂或環。
輸入緩衝區殘留：scanf 留下換行符，後續 getchar 需處理。

總結

頭插法與尾插法是單鏈表操作的「Hello World」。頭插法利用頭指針移動實現 O(1) 插入，尾插法必須維護尾指針才能達到 O(1) 插入，否則退化為 O(n²)。無頭結點版本通過「頭指針為空判斷空表」統一了邏輯，但插入/刪除首節點時仍需特殊處理頭指針更新。工程實踐中，帶頭結點 + 尾指針是構建高性能單鏈表的標準配置。