C語言單鏈表核心操作：初始化、插入、刪除與逆序完整實現

前言

單鏈表是最基礎的動態資料結構，掌握其核心操作是資料結構入門的必修課。本文提供帶頭結點的單鏈表完整實現，涵蓋初始化、有序插入、按值刪除、鏈表逆序四大核心操作。

一、節點結構與類型定義

typedef struct Node {
    int data;
    struct Node *next;
} Node, *Link;  // Link 為指向 Node 的指標類型

二、鏈表初始化：尾插法建立有序鏈表

Node* init(int len) {
    int i;
    Node *head, *p, *q;
    
    head = (Link)malloc(sizeof(Node));  // 創建頭結點
    head->data = 0;                     // 頭結點data存儲長度
    head->next = NULL;
    p = head;
    
    for (i = 0; i < len; i++) {
        q = (Link)malloc(sizeof(Node));
        q->data = 2 * i;                // 生成遞增數據：0, 2, 4, 6...
        q->next = NULL;
        p->next = q;                    // 尾插
        p = q;
        head->data++;                   // 更新長度計數
    }
    return head;
}

設計亮點：利用頭結點的 data 域存儲鏈表長度，避免額外變數。

三、有序插入：維持遞增序列

Node* insert(Node* head, int x) {
    Node *m = head->next;      // 從首個數據節點開始
    Node *tmp = (Link)malloc(sizeof(Node));
    tmp->data = x;
    tmp->next = NULL;
    
    // 遍歷尋找插入位置：m->data < x <= m->next->data
    while (m->next != NULL) {
        if (x > m->data && x <= m->next->data) {
            tmp->next = m->next;
            m->next = tmp;
            head->data++;       // 長度+1
            return head;
        }
        m = m->next;
    }
    
    // 若 x 最大，插入尾部
    if (x > m->data) {
        m->next = tmp;
        head->data++;
    }
    return head;
}

四、按值刪除：刪除所有匹配節點

Node* delete(Node* head, int x) {
    int found = 0;
    Node *m = head, *tmp;
    
    while (m->next != NULL) {
        if (m->next->data == x) {
            tmp = m->next;
            m->next = tmp->next;  // 斷鏈
            free(tmp);            // 釋放記憶體
            found = 1;
            head->data--;         // 長度-1
            // 注意：此處不移動 m，繼續檢查新的 m->next
        } else {
            m = m->next;          // 僅在未刪除時後移
        }
    }
    
    if (!found) {
        printf("不存在值為 %d 的節點\n", x);
    }
    return head;
}

關鍵細節：刪除後 m 不後移，可連續刪除相鄰的相同值節點。

五、鏈表逆序：三指標就地逆置

Node* reverse(Node* head) {
    // 空表或單節點直接返回
    if (head->next == NULL || head->next->next == NULL)
        return head;
    
    Node *t = NULL;
    Node *p = head->next;     // 當前節點
    Node *q = p->next;        // 下一節點
    
    while (q != NULL) {
        t = q->next;          // 保存下下節點
        q->next = p;          // 反轉指向
        p = q;                // 移動 p
        q = t;                // 移動 q
    }
    
    head->next->next = NULL;  // 原首節點變尾節點
    head->next = p;           // 頭結點指向新首節點
    return head;
}

算法圖解：

原始: head -> 1 -> 2 -> 3 -> NULL
過程: 
  p=1, q=2: 2->1, p=2, q=3
  p=2, q=3: 3->2, p=3, q=NULL
結果: head -> 3 -> 2 -> 1 -> NULL

六、列印與測試主程式

void printList(Node* head) {
    Node* p = head->next;  // 跳過頭結點
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

int main(int argc, char* argv[]) {
    if (argc < 4) {
        printf("用法: %s <長度> <插入值> <刪除值>\n", argv[0]);
        return 1;
    }
    
    int len = atoi(argv[1]);
    int insVal = atoi(argv[2]);
    int delVal = atoi(argv[3]);
    
    Node* list = init(len);
    printf("初始鏈表: ");
    printList(list);
    
    list = insert(list, insVal);
    printf("插入 %d 後: ", insVal);
    printList(list);
    
    list = delete(list, delVal);
    printf("刪除 %d 後: ", delVal);
    printList(list);
    
    list = reverse(list);
    printf("逆序後: ");
    printList(list);
    
    return 0;
}

七、複雜度分析總結

單鏈表操作的核心在於「指標調整順序」與「邊界條件處理」。建議初學者多繪圖演練各操作過程，特別注意頭結點的特殊角色與空指標檢查。