4、单向链表的删除操作：删除头节点、删除尾节点、删除指定节点

链表操作中，删除节点是最容易出bug的地方之一。我刚开始写链表时，经常因为指针操作不当导致程序崩溃。说白了，删除操作的核心就一句话：把要删的节点从链中摘出来，然后释放它的内存。但具体怎么摘，头、尾、中间节点各有讲究。

4.1 删除头节点

删除头节点是最简单的。你想想看，头节点就是链表的第一个节点，只要把head指针往后挪一位，再把原来的头节点释放掉就行了。

// 删除头节点
Node* deleteHead(Node* head) {
    if (head == NULL) {
        printf("链表为空，无法删除\n");
        return NULL;
    }
    
    Node* temp = head;      // 暂存头节点
    head = head->next;      // 头指针后移
    free(temp);             // 释放原头节点
    return head;
}
注意：删除头节点后，一定要把新的头指针返回给调用者。我见过有人忘记返回，结果链表就丢了。

这里有个细节：如果链表只有一个节点，删除后head就变成NULL了。代码里已经处理了这种情况——head->next是NULL，赋值给head后返回NULL，逻辑上是正确的。

4.2 删除尾节点

删除尾节点比删除头节点麻烦一些。为什么呢？因为单向链表只能往后走，不能回头。要删除尾节点，你得先找到倒数第二个节点，然后把它的next置为NULL。

// 删除尾节点
Node* deleteTail(Node* head) {
    if (head == NULL) {
        printf("链表为空\n");
        return NULL;
    }
    
    // 只有一个节点的情况
    if (head->next == NULL) {
        free(head);
        return NULL;
    }
    
    Node* current = head;
    // 找到倒数第二个节点
    while (current->next->next != NULL) {
        current = current->next;
    }
    
    free(current->next);    // 释放尾节点
    current->next = NULL;   // 新尾节点next置空
    return head;
}
小技巧：判断条件 current->next->next != NULL 可能看着有点绕。其实就是在找「下一个节点的下一个节点」不为空的节点。当这个条件不成立时，current就是倒数第二个节点。

我曾经在项目中犯过一个低级错误：释放尾节点后忘了把新尾节点的next置为NULL。结果遍历链表时，最后一个节点明明已经释放了，但它的next指针还指向一块野内存，程序跑着跑着就崩了。嗯，从那以后我每次删除节点都会检查指针的完整性。

4.3 删除指定节点

删除指定节点分两种情况：

  • 要删的是头节点——直接调用删除头节点的逻辑
  • 要删的是中间或尾节点——先找到目标节点的前一个节点
// 删除指定值的节点
Node* deleteNode(Node* head, int value) {
    if (head == NULL) return NULL;
    
    // 如果要删除的是头节点
    if (head->data == value) {
        Node* temp = head;
        head = head->next;
        free(temp);
        return head;
    }
    
    Node* current = head;
    // 查找目标节点的前一个节点
    while (current->next != NULL && current->next->data != value) {
        current = current->next;
    }
    
    // 没找到
    if (current->next == NULL) {
        printf("未找到值为%d的节点\n", value);
        return head;
    }
    
    // 删除目标节点
    Node* target = current->next;
    current->next = target->next;
    free(target);
    
    return head;
}
核心要点：删除指定节点时，关键是要找到目标节点的前一个节点。因为单向链表没有前驱指针，只能通过前一个节点来修改链接关系。

4.4 三种删除操作的对比

操作类型 时间复杂度 特殊处理 常见错误
删除头节点 O(1) 链表为空或只有一个节点 忘记返回新头指针
删除尾节点 O(n) 需要遍历到倒数第二个节点 忘记将新尾节点next置NULL
删除指定节点 O(n) 目标节点是头节点时单独处理 遍历时越界访问空指针

4.5 删除操作的完整示例

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

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

// 创建节点（辅助函数）
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 打印链表（辅助函数）
void printList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

int main() {
    // 创建链表: 1 -> 2 -> 3 -> 4 -> NULL
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    
    printf("原始链表: ");
    printList(head);
    
    // 删除头节点
    head = deleteHead(head);
    printf("删除头节点后: ");
    printList(head);
    
    // 删除尾节点
    head = deleteTail(head);
    printf("删除尾节点后: ");
    printList(head);
    
    // 删除指定节点（值为3）
    head = deleteNode(head, 3);
    printf("删除值为3的节点后: ");
    printList(head);
    
    return 0;
}

4.6 删除操作的核心流程图

单向链表删除操作流程图 开始删除操作 链表为空？ (head == NULL) 是 返回 NULL 否 删除类型？ 头节点 删除头节点 head = head->next; free(temp); 尾节点 删除尾节点 遍历到倒数第二个节点 指定节点 删除指定节点 查找目标节点的前一个节点 返回新的头指针

4.7 避坑指南

我曾经踩过的坑：
  1. 忘记检查空指针——删除操作前一定要判断链表是否为空，否则程序直接崩溃。
  2. 释放后继续使用——free之后不要再访问那块内存，把它想象成「已经还给系统了」。
  3. 遍历条件写错——比如 while(current->next != NULL) 和 while(current != NULL) 差别很大，写错了要么漏掉节点，要么访问野指针。
  4. 头节点更新不及时——删除头节点后，调用者拿到的还是旧的头指针，链表就断了。
我的个人习惯：每次写完删除操作，我都会画一个简单的链表图，把指针的指向变化一步步画出来。别嫌麻烦，画一遍比看十遍代码都管用。尤其是刚学链表的时候，纸上画图能帮你把逻辑理得清清楚楚。

删除操作是链表中最容易出问题的环节，但也是最能锻炼指针思维的地方。你想想看，一个不小心就可能把整个链表搞丢，或者内存泄漏。但只要掌握了「先备份、再修改、后释放」这个原则，大部分问题都能避免。

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

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