删除双向链表中最大值元素的程序崩溃问题排查

我在实现删除双向链表中最大值（原文为"greatest"，避免与"largest"混淆）元素的功能时遇到问题：当链表中仅有一个最大值元素时程序运行正常，但当链表存在多个最大值元素（例如最后两个元素均为最大值）时，程序会崩溃。我确定问题出在节点地址的管理上。

原始代码 #

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

typedef struct node
{
    struct node* prev;
    int value;
    struct node* next;
} node;

node* allocateNode(int value);
node* addToEnd(node* head, int value);
node* makeList(node* head, int n);
node* deleteMaxElement(node* head);
void freeMemory(node* head);

int main()
{
    node* head = NULL;
    int n = 0;

    printf("Enter number of elements: ");
    if (!(scanf("%d", &n) == 1))
        return 0;

    head = makeList(head, n);
    head = deleteMaxElement(head);

    if (n > 1)
    {
        node* element = head;
        printf("%d ", element->value);
        while(element->next != NULL)
        {
            element = element->next;
            printf("%d ", element->value);
        }
        printf("\n");
        freeMemory(head);
    }

    return 0;
}

node* makeList(node* head, int n)
{
    int value = 0;
    if (n == 0)
        return head;

    printf("Enter value of 1 node: ");
    if (scanf("%d", &value) == 1)
    {
        head = allocateNode(value);
        for (int i = 1; i < n; i++)
        {
            printf("Enter value of %d node: ", i + 1);
            if(scanf("%d", &value) == 1)
                head = addToEnd(head, value);
        }
    }
    return head;
}

node* allocateNode(int value)
{
    node* newNode = (node*)malloc(sizeof(node));
    newNode->prev = NULL;
    newNode->next = NULL;
    newNode->value = value;
    return newNode;
}

node* addToEnd(node* head, int value)
{
    node* newNode = allocateNode(value);
    node* element = head;

    while (element->next != NULL)
        element = element->next;

    element->next = newNode;
    newNode->prev = element;

    return head;
}

node* deleteMaxElement(node* head)
{
    int max = head->value;
    node* element = head;
    // finds max element in list
    while (element->next != NULL)
    {
        element = element->next;
        if (element->value > max)
            max = element->value;
    }
    // max element is in the list head
    int firstElementDeleted = 0;
    if (head->value == max)
    {
        node* temp = head->next;
        free(head);
        head = temp;
        firstElementDeleted = 1;
    }
    // max elements is not in the list head
    element = head;
    while (element->next != NULL)
    {
        node* temp = NULL;
        if (element->value == max)
        {   
            if (!firstElementDeleted)
                (element->prev)->next = element->next;
            else
                head = element->next;
            temp = element->next;
            free(element);
            element = temp;
            continue;
        }
        element = element->next;
    }
    // max elements is in the last node
    if (element->value == max)
    {
        (element->prev)->next = NULL;
        free(element);
    }
    return head;
}

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

问题根源分析 #

1. 头节点删除后的标记逻辑错误：删除头节点后，遍历后续节点时错误地重置head，未维护链表的双向关联，导致后续节点的prev指针失效。
2. 最后一个节点删除的空指针风险：若链表仅剩最后一个最大值节点，element->prev为NULL，此时访问(element->prev)->next会触发崩溃。
3. 节点删除时的指针更新不完整：删除中间节点时，未更新下一个节点的prev指针，破坏了双向链表的结构。

修复后的代码 #

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

typedef struct node
{
    struct node* prev;
    int value;
    struct node* next;
} node;

node* allocateNode(int value);
node* addToEnd(node* head, int value);
node* makeList(node* head, int n);
node* deleteMaxElement(node* head);
void freeMemory(node* head);

int main()
{
    node* head = NULL;
    int n = 0;

    printf("Enter number of elements: ");
    if (!(scanf("%d", &n) == 1))
        return 0;

    head = makeList(head, n);
    head = deleteMaxElement(head);

    // 修复：判断链表是否为空，而非依赖原始n值
    if (head != NULL)
    {
        node* element = head;
        printf("%d ", element->value);
        while(element->next != NULL)
        {
            element = element->next;
            printf("%d ", element->value);
        }
        printf("\n");
        freeMemory(head);
    }

    return 0;
}

node* makeList(node* head, int n)
{
    int value = 0;
    if (n == 0)
        return head;

    printf("Enter value of 1 node: ");
    if (scanf("%d", &value) == 1)
    {
        head = allocateNode(value);
        for (int i = 1; i < n; i++)
        {
            printf("Enter value of %d node: ", i + 1);
            if(scanf("%d", &value) == 1)
                head = addToEnd(head, value);
        }
    }
    return head;
}

node* allocateNode(int value)
{
    node* newNode = (node*)malloc(sizeof(node));
    newNode->prev = NULL;
    newNode->next = NULL;
    newNode->value = value;
    return newNode;
}

node* addToEnd(node* head, int value)
{
    node* newNode = allocateNode(value);
    node* element = head;

    while (element->next != NULL)
        element = element->next;

    element->next = newNode;
    newNode->prev = element;

    return head;
}

node* deleteMaxElement(node* head)
{
    if (head == NULL)
        return NULL;

    // 遍历整个链表找到最大值
    int max = head->value;
    node* element = head;
    while (element != NULL)
    {
        if (element->value > max)
            max = element->value;
        element = element->next;
    }

    // 遍历删除所有最大值节点
    element = head;
    while (element != NULL)
    {
        node* next_node = element->next; // 提前保存下一个节点，避免删除后丢失
        if (element->value == max)
        {
            if (element->prev != NULL)
            {
                // 非头节点：更新前驱的next指针
                element->prev->next = element->next;
            }
            else
            {
                // 头节点：更新链表头指针
                head = element->next;
            }

            if (element->next != NULL)
            {
                // 非尾节点：更新后继的prev指针
                element->next->prev = element->prev;
            }

            free(element);
        }
        element = next_node;
    }

    return head;
}

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

关键修改说明 #

1. 最大值查找逻辑优化：遍历整个链表（包括最后一个节点）确保找到正确的最大值。
2. 统一节点删除逻辑：
   • 提前保存下一个节点，避免删除当前节点后无法继续遍历
   • 分别处理头节点、中间节点、尾节点的指针更新，确保双向链表关联完整
   • 删除节点时同时更新前驱的next和后继的prev指针
3. 边界条件修复：处理链表为空、仅剩一个节点的情况，避免空指针访问
4. 输出逻辑修复：改为判断head是否为空，而非依赖原始n值，确保删除后链表为空时不会出错

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