C語言實現單鏈表頭插法與尾插法建表（無頭結點版）完整代碼

單鏈表建表的兩種經典模式：頭插法（新節點插入頭部，輸入順序逆序存儲）與尾插法（新節點追加尾部，輸入順序正序存儲）。本文提供無頭結點版本的完整可編譯實現，包含初始化、建表、打印、主函數測試。

完整程序代碼

#include 
#include 
#include 

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

// 初始化：置空頭指針
void InitList(Node* pNode) {
    pNode = NULL;
    printf("%s: 初始化完成\n", __FUNCTION__);
}

// 打印鏈表
void PrintList(Node* pNode) {
    if (!pNode) {
        printf("%s: 鏈表為空\n", __FUNCTION__);
        return;
    }
    while (pNode) {
        printf("%d ", pNode->element);
        pNode = pNode->next;
    }
    printf("\n");
}

// 頭插法建表
Node* HeadInsert(Node* pNode) {
    Node* pInsert = (Node*)malloc(sizeof(Node));
    if (!pInsert) return NULL;
    memset(pInsert, 0, sizeof(Node));
    scanf("%d", &pInsert->element);
    pInsert->next = NULL;
    
    if (pInsert->element <= 0) {
        free(pInsert);
        printf("%s: 首值非正，建表失敗\n", __FUNCTION__);
        return NULL;
    }
    
    while (pInsert->element > 0) {
        if (!pNode) {
            pNode = pInsert;           // 首節點
        } else {
            pInsert->next = pNode;     // 關鍵：新節點指向原頭
            pNode = pInsert;           // 更新頭指針
        }
        pInsert = (Node*)malloc(sizeof(Node));
        if (!pInsert) break;
        memset(pInsert, 0, sizeof(Node));
        scanf("%d", &pInsert->element);
        pInsert->next = NULL;
    }
    free(pInsert);  // 釋放最後預分配未用節點
    printf("%s: 頭插法建表成功\n", __FUNCTION__);
    return pNode;
}

// 尾插法建表
Node* TailInsert(Node* pNode) {
    Node *pInsert, *pMove = pNode;
    pInsert = (Node*)malloc(sizeof(Node));
    if (!pInsert) return NULL;
    memset(pInsert, 0, sizeof(Node));
    scanf("%d", &pInsert->element);
    pInsert->next = NULL;
    
    if (pInsert->element <= 0) {
        free(pInsert);
        printf("%s: 首值非正，建表失敗\n", __FUNCTION__);
        return NULL;
    }
    
    while (pInsert->element > 0) {
        if (!pNode) {
            pNode = pInsert;
            pMove = pNode;             // 尾游標初始化
        } else {
            while (pMove->next) pMove = pMove->next;  // 定位尾節點
            pMove->next = pInsert;
            pMove = pInsert;           // 尾游標後移
        }
        pInsert = (Node*)malloc(sizeof(Node));
        if (!pInsert) break;
        memset(pInsert, 0, sizeof(Node));
        scanf("%d", &pInsert->element);
        pInsert->next = NULL;
    }
    free(pInsert);
    printf("%s: 尾插法建表成功\n", __FUNCTION__);
    return pNode;
}

int main() {
    Node* pList = NULL;
    InitList(pList);
    PrintList(pList);
    
    printf("輸入數據（負數結束）測試頭插法：");
    pList = HeadInsert(pList);   // 輸入：1 2 3 -1 => 鏈表：3 2 1
    PrintList(pList);
    
    printf("再次輸入測試尾插法：");
    pList = TailInsert(pList);   // 輸入：4 5 6 -1 => 鏈表：3 2 1 4 5 6
    PrintList(pList);
    
    return 0;
}

頭插法 vs 尾插法核心差異

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

上述尾插法每次插入都從頭遍歷到尾，總時間 O(n²)。實際工程中應維護 pTail 指針：

Node *pHead = NULL, *pTail = NULL;
// 插入時：
if (!pHead) { pHead = pTail = pInsert; }
else { pTail->next = pInsert; pTail = pInsert; }

無頭結點版本的痛點

• 頭插法需返回新頭指針，調用者必須接收。
• 尾插法首次插入需同時初始化 pHead 與 pMove。
• 所有操作均需特判空鏈表。

結論：教學理解原理用無頭結點版本；實際工程請直接使用帶頭結點單鏈表，統一邏輯、消除特判、降低認知負荷。