50、链表操作：头插法、尾插法、删除节点

链表这东西，说简单也简单，说难也难。我见过不少写了三年代码的同事，一碰到链表删除节点就翻车。说白了，链表就是一堆节点串起来，每个节点里存着数据和指向下一个节点的指针。但就是这「指针」二字，坑了多少人。

今天咱们就把链表的三个基本操作——头插法、尾插法、删除节点——彻底讲透。嗯，我保证，看完这一章，你写链表代码的手不会再抖。

链表节点的定义

先看最基本的节点结构。我个人习惯用 typedef 把结构体重命名一下，这样写起来清爽很多。

typedef struct Node {
    int data;           // 数据域
    struct Node *next;  // 指针域，指向下一个节点
} Node;

这里要注意：struct Node *next 不能写成 Node *next，因为 typedef 还没生效呢。这个顺序问题，我当年刚学的时候也栽过跟头。

头插法

头插法，就是把新节点插到链表的最前面。每次插入的新节点都成为新的头节点。

为什么要用头插法？最常见的场景就是「逆序构建链表」。你想想看，如果你有一组数据，想用链表存起来，并且希望遍历时是逆序的，头插法就是最佳选择。

Node *headInsert(Node *head, int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return head;
    }
    newNode->data = data;
    newNode->next = head;  // 新节点指向原来的头节点
    head = newNode;        // 更新头节点
    return head;
}

核心就两行：newNode->next = head 和 head = newNode。顺序不能反。我曾经见过有人写成 head = newNode; newNode->next = head;——这等于新节点指向了自己，链表直接成环了。

⚠️ 注意：头插法插入后，原来的头节点变成了第二个节点。如果你有外部指针指向原来的头节点，那个指针就「过时」了。所以一定要记得更新头指针。

尾插法

尾插法，就是把新节点加到链表末尾。这样构建出来的链表，顺序和输入顺序一致。

尾插法比头插法麻烦一点，因为你得先找到尾巴。如果每次都从头遍历到末尾，效率是 O(n)。我建议维护一个尾指针，这样插入就是 O(1)。

Node *tailInsert(Node *head, int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return head;
    }
    newNode->data = data;
    newNode->next = NULL;

    if (head == NULL) {
        // 链表为空，新节点就是头节点
        return newNode;
    }

    Node *cur = head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = newNode;
    return head;
}

这里有个细节：如果链表为空，新节点既是头也是尾。很多新手会忘记这个判断，直接去遍历，结果 head->next 就段错误了。

💡 小技巧：如果你频繁使用尾插法，可以定义一个结构体来同时保存头指针和尾指针：typedef struct { Node *head; Node *tail; } LinkedList;。这样插入时直接操作 tail，不用每次都遍历。

删除节点

删除节点是链表操作里最容易出错的。为什么？因为你要处理指针的重新连接，还要释放内存。漏了任何一步，要么内存泄漏，要么野指针。

删除节点分三种情况：

  1. 删除头节点：直接让 head 指向第二个节点，然后释放原头节点。
  2. 删除中间节点：找到待删节点的前一个节点，让它跳过待删节点，指向待删节点的下一个节点。
  3. 删除尾节点：找到倒数第二个节点，把它的 next 置为 NULL，然后释放尾节点。
Node *deleteNode(Node *head, int target) {
    if (head == NULL) {
        return NULL;
    }

    // 删除头节点
    if (head->data == target) {
        Node *temp = head;
        head = head->next;
        free(temp);
        return head;
    }

    // 删除非头节点
    Node *prev = head;
    Node *cur = head->next;
    while (cur != NULL) {
        if (cur->data == target) {
            prev->next = cur->next;
            free(cur);
            break;
        }
        prev = cur;
        cur = cur->next;
    }

    return head;
}

嗯，这里要注意：删除节点后，那个节点就不存在了。如果你之前有其他指针指向它，那些指针就成了野指针。我在项目中遇到过这样的 bug——一个全局指针指向了某个节点，节点被删了，全局指针还在用，结果程序随机崩溃，查了两天才找到原因。

⚠️ 避坑指南：我曾经在删除节点后忘记把被删节点的 next 置 NULL 再 free，结果 free 之后那块内存被回收，但 next 指针还在。后来那块内存被重新分配给了别的变量，next 指针就变成了一个完全无关的地址——这就是典型的「悬空指针」。

三种操作对比

操作 时间复杂度 空间复杂度 适用场景
头插法 O(1) O(1) 逆序构建链表、栈
尾插法（无尾指针） O(n) O(1) 顺序构建链表
尾插法（有尾指针） O(1) O(1) 频繁尾部插入
删除节点 O(n) O(1) 按值删除

核心逻辑流程图

下面这张图展示了链表三种操作的核心流程。我特意把容易出错的地方标红了，你写代码的时候可以对照着看。

链表三种操作核心流程 头插法 1. 创建新节点 2. newNode->next = head 3. head = newNode ⚠ 顺序不能反！ 插入前: head → [A] → [B] 插入后: head → [新] → [A] → [B] 新节点成为头节点 时间复杂度: O(1) 适用: 逆序构建、栈 尾插法 1. 创建新节点 2. 找到尾节点 3. tail->next = newNode ⚠ 空链表要单独处理 插入前: [A] → [B] → NULL 插入后: [A] → [B] → [新] → NULL 新节点成为尾节点 时间复杂度: O(n) / O(1)有尾指针 适用: 顺序构建 删除节点 1. 找到待删节点 2. prev->next = cur->next 3. free(cur) ⚠ 分三种情况处理 删除前: [A] → [B] → [C] 删除B后: [A] → [C] B的内存被释放 时间复杂度: O(n) ⚠ 注意悬空指针

完整示例：综合使用三种操作

下面这个例子，把三种操作串在一起。先尾插法构建链表，再头插法插入一个节点，最后删除指定节点。你可以跑一下看看效果。

#include <stdio.h>
#include <stdlib.h>

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

void printList(Node *head) {
    Node *cur = head;
    while (cur != NULL) {
        printf("%d -> ", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

int main() {
    Node *head = NULL;

    // 尾插法构建链表: 1 -> 2 -> 3
    head = tailInsert(head, 1);
    head = tailInsert(head, 2);
    head = tailInsert(head, 3);
    printf("尾插法构建: ");
    printList(head);

    // 头插法插入 0: 0 -> 1 -> 2 -> 3
    head = headInsert(head, 0);
    printf("头插法插入0: ");
    printList(head);

    // 删除节点 2: 0 -> 1 -> 3
    head = deleteNode(head, 2);
    printf("删除节点2: ");
    printList(head);

    // 释放剩余节点
    Node *cur = head;
    while (cur != NULL) {
        Node *temp = cur;
        cur = cur->next;
        free(temp);
    }

    return 0;
}
📌 核心要点：
  • 头插法：新节点指向头，更新头指针。顺序不能错。
  • 尾插法：找到尾巴再插入。空链表要单独处理。
  • 删除节点：分头、中、尾三种情况。记得 free，记得处理指针。
  • 所有操作都要检查 malloc 返回值。内存分配失败不是小事。

链表操作，说白了就是指针的重新指向。你只要画清楚每个节点之间的连接关系，代码自然就写对了。我每次写链表代码之前，都会在草稿纸上画一遍指针的指向变化——这个习惯帮我避免了很多低级错误。

嗯，链表这块就讲到这里。记住：多画图，少踩坑。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →