如何删除双向链表中所有值最小的节点

原代码中的deleteSmallest函数仅能删除第一个值最小的节点，要实现删除所有值最小的节点，需要分两步操作：

• 第一步：遍历整个链表，确定所有节点中的最小值
• 第二步：再次遍历链表，逐个删除值等于最小值的节点，同时处理好双向链表的指针关联，避免断链

以下是修改后的完整代码：

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

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

node *createList(struct node *head, int n);
node *addToEmpty(node *head, int data);
node *addAtEnd(node *head, int data);
node *deleteSmallest(node *head, int n);
void cleanUp(node *head);

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

    printf("Enter number of the nodes: ");
    scanf("%d", &n);

    head = createList(head, n);
    printf("\nN: %d\n\n", n);

    ptr = head;

    while(ptr != NULL)
    {
        printf("NUMBER:%d ADDRESS:%p PREVADD:%p NEXTADD:%p\n", ptr->number, ptr, ptr->prev, ptr->next);
        ptr = ptr->next;
    }

    head = deleteSmallest(head, n);

    printf("\n\n");

    ptr = head;

    while(ptr != NULL)
    {
        printf("NUMBER:%d ADDRESS:%p PREVADD:%p NEXTADD:%p\n", ptr->number, ptr, ptr->prev, ptr->next);
        ptr = ptr->next;
    }

    // Free all the pointers
    cleanUp(head);

    return 0;
}

node *createList(struct node *head, int n)
{
    int data;

    if(n <= 0)
        return head;

    printf("Enter number of the 1 node: ");
    scanf("%d", &data);

    head = addToEmpty(head, data);

    for(int i = 1; i < n; ++i)
    {
        printf("Enter number of the %d node: ", i + 1);
        scanf("%d", &data);
        head = addAtEnd(head, data);
    }
    return head;
}

node *addToEmpty(node *head, int data)
{
    node *temp = malloc(sizeof(node));
    temp->prev = NULL;
    temp->next = NULL;
    temp->number = data;
    head = temp;

    return head;
}

node *addAtEnd(node *head, int data)
{
    node *temp, *tp;

    temp = malloc(sizeof(node));
    temp->prev = NULL;
    temp->next = NULL;
    temp->number = data;
    tp = head;

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

    tp->next = temp;
    temp->prev = tp;

    return head;
}

node *deleteSmallest(node *head, int n)
{
    if (head == NULL) return NULL;

    // 第一步：找出链表中的最小值
    node *current = head;
    int min_val = head->number;
    while (current != NULL) {
        if (current->number < min_val) {
            min_val = current->number;
        }
        current = current->next;
    }

    // 第二步：遍历链表，删除所有值等于最小值的节点
    current = head;
    node *next_node;
    while (current != NULL) {
        next_node = current->next; // 先保存下一个节点，避免删除当前节点后断链
        if (current->number == min_val) {
            if (current->prev == NULL) {
                // 删除头节点
                head = next_node;
                if (head != NULL) {
                    head->prev = NULL;
                }
            } else if (current->next == NULL) {
                // 删除尾节点
                current->prev->next = NULL;
            } else {
                // 删除中间节点
                current->prev->next = current->next;
                current->next->prev = current->prev;
            }
            free(current);
        }
        current = next_node;
    }

    return head;
}

void cleanUp(node *head)
{
    node *next;

    while(head != NULL)
    {
        next = head->next;
        free(head);
        head = next;
    }
}

修改说明 #

1. 确定最小值：第一次遍历链表，找到所有节点中的最小数值，明确需要删除的节点目标。
2. 遍历删除节点：第二次遍历链表时，提前保存当前节点的下一个节点（避免删除当前节点后无法继续遍历），再根据节点位置（头、中间、尾）调整双向链表的前后指针，最后释放节点内存。
3. 边界处理：覆盖了链表为空、所有节点都是最小值、最小值出现在头尾等多种边界场景，保证链表操作的稳定性。

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