C / C++ / 系统课时

删除节点时如何不断链

删除节点时如何不断链

删除单链表节点最容易出错的地方,是在释放目标节点后才去读取它的 next。正确做法是先让链表绕过目标节点,再释放内存。本节实现按位置删除,并覆盖头节点、尾节点、空链表和越界位置。

学习目标

  • 理解删除节点时前驱、目标和后继三者的关系
  • 掌握“先改链,再释放”的安全顺序
  • 能处理头删、尾删和非法删除位置

删除的核心不是 free

对非头节点删除,假设 prev 指向目标节点的前驱,target 指向待删除节点。真正决定链表是否连续的是这一句:

prev->next = target->next

完成它以后,链表已经绕过 target。此时再执行 free(target),不会影响剩余节点之间的连接。

删除节点时安全修改指针的顺序

如果先 free(target),随后再访问 target->next,就是读取已经释放的内存,行为未定义。程序有时看似还能运行,但也可能崩溃或破坏链表,因此不能依赖这种偶然结果。

完整实现

下面使用 0-based 位置删除节点。函数通过 deleted_value 返回被删值;如果传入 NULL,则只删除而不返回值。

c
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

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

bool push_back(Node **head, int value) {
    Node *new_node = malloc(sizeof(*new_node));
    if (new_node == NULL) {
        return false;
    }
    new_node->value = value;
    new_node->next = NULL;

    if (*head == NULL) {
        *head = new_node;
        return true;
    }

    Node *p = *head;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = new_node;
    return true;
}

bool delete_at(Node **head, size_t position, int *deleted_value) {
    if (head == NULL || *head == NULL) {
        return false;
    }

    if (position == 0) {
        Node *target = *head;
        *head = target->next;
        if (deleted_value != NULL) {
            *deleted_value = target->value;
        }
        free(target);
        return true;
    }

    Node *prev = *head;
    for (size_t i = 1; i < position; ++i) {
        if (prev->next == NULL) {
            return false;
        }
        prev = prev->next;
    }

    Node *target = prev->next;
    if (target == NULL) {
        return false;
    }

    // 先让前驱跨过目标节点,再释放目标节点。
    prev->next = target->next;
    if (deleted_value != NULL) {
        *deleted_value = target->value;
    }
    free(target);
    return true;
}

void print_list(const Node *head) {
    for (const Node *p = head; p != NULL; p = p->next) {
        printf("%d", p->value);
        if (p->next != NULL) {
            printf(" -> ");
        }
    }
    printf("\n");
}

void free_list(Node *head) {
    while (head != NULL) {
        Node *next = head->next;
        free(head);
        head = next;
    }
}

int main(void) {
    Node *head = NULL;
    int deleted = 0;

    push_back(&head, 10);
    push_back(&head, 20);
    push_back(&head, 30);
    push_back(&head, 40);

    delete_at(&head, 1, &deleted);
    printf("deleted: %d\n", deleted);
    print_list(head);

    delete_at(&head, 0, &deleted);
    printf("deleted: %d\n", deleted);
    print_list(head);

    delete_at(&head, 1, &deleted);
    printf("deleted: %d\n", deleted);
    print_list(head);

    bool ok = delete_at(&head, 3, &deleted);
    printf("delete position 3: %s\n", ok ? "success" : "invalid position");

    free_list(head);
    return 0;
}

预期输出

text
deleted: 20
10 -> 30 -> 40
deleted: 10
30 -> 40
deleted: 40
30
delete position 3: invalid position

头节点与尾节点的区别

删除头节点时没有前驱可修改,因此必须让 *head 直接指向旧头节点的后继,然后释放旧头节点。若链表只有一个节点,target->next 本来就是 NULL,删除后 *head 自然变为 NULL。

删除尾节点不需要特殊分支。尾节点的 target->next 为 NULL,执行 prev->next = target->next 后,前驱自动成为新的尾节点。

常见错误与验证顺序

最危险的错误是先释放再取后继;另一类错误是只释放目标节点,却忘记修改前驱的 next,这样前驱仍保存着悬空指针。还要避免在位置越界时继续解引用 prev->next。

验证删除逻辑时,至少检查四种情况:删除中间节点、删除头节点、删除尾节点、删除非法位置。每次成功删除后都打印链表,确认剩余节点顺序正确;失败时则确认链表没有被修改。

按位置删除通常需要先遍历到前驱,所以时间复杂度为 O(n)O(n);若调用者已经持有前驱指针,则实际摘链只需要 O(1)O(1)。无论哪种情况,顺序都应保持一致:先保存或重连仍需使用的指针,再释放目标节点。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

删除节点时如何不断链

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通