删除单链表中的最小值节点

要从单向链表中删除最小值节点，我们需要完成以下几个步骤：

找到最小值节点

记录其前驱节点（为了删除时能连接前后节点）

执行删除操作

处理特殊情况（如头节点是最小值的情况）

实现方法
C语言实现

#include <stdlib.h>

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

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 删除链表中的最小值节点
void deleteMinNode(Node** headRef) {
    if (*headRef == NULL) {
        printf("链表为空\n");
        return;
    }

    Node* current = *headRef;
    Node* prev = NULL;
    Node* minNode = *headRef;
    Node* prevMin = NULL;

    // 遍历链表寻找最小值节点及其前驱
    while (current != NULL) {
        if (current->data < minNode->data) {
            minNode = current;
            prevMin = prev;
        }
        prev = current;
        current = current->next;
    }

    // 删除最小值节点
    if (prevMin == NULL) {
        // 最小值是头节点
        *headRef = minNode->next;
    } else {
        // 最小值不是头节点
        prevMin->next = minNode->next;
    }

    free(minNode);
}

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

int main() {
    Node* head = createNode(5);
    head->next = createNode(2);
    head->next->next = createNode(8);
    head->next->next->next = createNode(1);
    head->next->next->next->next = createNode(3);

    printf("原始链表: ");
    printList(head);

    deleteMinNode(&head);

    printf("删除最小值后: ");
    printList(head);

    // 释放链表内存
    while (head != NULL) {
        Node* temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}

算法分析
时间复杂度：O(n)，需要遍历整个链表一次来找到最小值

空间复杂度：O(1)，只使用了固定数量的指针变量

特殊情况处理
空链表：直接返回，不执行任何操作

多个最小值：此代码会删除第一个遇到的最小值节点

头节点是最小值：需要特殊处理以更新头指针

扩展：删除所有最小值节点
如果需要删除所有最小值节点（当有多个相同的最小值时），可以稍作修改：

    if (*headRef == NULL) return;

    // 首先找到最小值
    int minVal = (*headRef)->data;
    Node* current = (*headRef)->next;
    while (current != NULL) {
        if (current->data < minVal) {
            minVal = current->data;
        }
        current = current->next;
    }

    // 删除所有值为minVal的节点
    Node* dummy = createNode(0); // 哑节点简化操作
    dummy->next = *headRef;
    Node* prev = dummy;
    current = *headRef;

    while (current != NULL) {
        if (current->data == minVal) {
            prev->next = current->next;
            free(current);
            current = prev->next;
        } else {
            prev = current;
            current = current->next;
        }
    }

    *headRef = dummy->next;
    free(dummy);
}

这种方法使用哑节点(dummy node)简化了边界条件的处理，特别是当头节点需要被删除时。