删除双向链表单个节点后head指针异常的原因及修复方案

问题原因 #

当删除的是链表中唯一的节点（即头节点）时，代码存在两个核心问题：

1. 传值参数无法修改外部指针：deleteNode的参数node是传值传递，函数内部的node只是外部头指针的副本。末尾的node = NULL只会修改这个副本的指向，完全不会影响外部的头指针变量。外部头指针仍然指向已被free释放的内存，这块内存已不属于程序，访问其键值自然会得到随机垃圾数据。
2. 未处理头节点删除后的指针同步：链表仅存一个节点时，删除后链表应为空，但代码没有同步更新外部头指针，导致头指针沦为野指针。

修复方法 #

方法一：使用双重指针传入头指针

通过传入头指针的指针（Node** head），让函数直接修改外部的头指针变量，代码如下：

void deleteNode(Node** head, Node* node) {
    if(node == NULL || head == NULL) {
        return;
    }
    
    // 更新前驱与后继节点的链接
    if(node->next != NULL) {
         node->next->prev = node->prev;
    }
    if(node->prev != NULL) {
         node->prev->next = node->next;
    }
    
    // 若删除的是头节点，同步更新外部头指针
    if(*head == node) {
        *head = node->next; // 唯一节点时，node->next为NULL，头指针被置空
    }

    free(node);
}

调用时传入头指针的地址：deleteNode(&head, nodeToDelete);

方法二：让函数返回新的头指针

函数执行后返回更新后的头指针，调用者用返回值更新自身的头指针变量：

Node* deleteNode(Node* head, Node* node) {
    if(node == NULL) {
        return head;
    }
    
    // 更新前驱与后继节点的链接
    if(node->next != NULL) {
         node->next->prev = node->prev;
    }
    if(node->prev != NULL) {
         node->prev->next = node->next;
    }
    
    // 若删除的是头节点，返回新的头指针
    if(head == node) {
        head = node->next;
    }

    free(node);
    return head;
}

调用时更新头指针：head = deleteNode(head, nodeToDelete);

内容的提问来源于stack exchange，提问作者Raj Vichare