试编写在带头结点的单链表l中删除（一个）最小值结点的（高效）算法。

算法步骤如下：

1. 定义一个指针p指向头结点的下一个结点，定义一个指针pre指向头结点。

2. 定义一个变量min记录当前最小值，初始值为p所指结点的值。

3. 从p所指结点开始遍历整个链表，如果遇到比min更小的值，就更新min的值，并记录下该结点的前驱结点pre。

4. 遍历完整个链表后，如果min的值没有发生变化，说明链表中只有一个结点，直接删除该结点即可。

5. 否则，将pre的next指针指向min所在的结点的next指针，即删除min所在的结点。

6. 释放min所在的结点的内存空间。

7. 返回头结点。

该算法的时间复杂度为O(n)，其中n为链表的长度。

相关问题

试编写带头结点的单链表L中删除一个最小值结点的高效算法（假设最小值结点 是唯一的用C语言实现

在C语言中，我们可以创建一个指向头结点的指针，并维护两个指针：`current` 和 `minNode`。`current` 指向当前节点，`minNode` 初始时指向头结点。如果找到比当前最小值还小的节点，则更新 `minNode`。遍历链表的同时，一旦遇到一个等于或大于 `minNode` 指向的节点，就删除它并继续前进。

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

// 定义链表节点结构体
typedef struct ListNode {
    int val;
    struct ListNode* next;
} ListNode;

// 删除最小值节点函数
ListNode* deleteMin(ListNode* head) {
    if (head == NULL || head->next == NULL) { // 如果链表为空或只有一个元素
        free(head);
        return NULL;
    }
    
    ListNode* minNode = head; // 初始化最小值节点为头节点
    ListNode* current = head->next;
    
    while (current != NULL) {
        if (current->val < minNode->val) { // 找到新最小值
            minNode = current;
        }
        current = current->next;
    }

    // 删除最小值节点
    if (head == minNode) { // 如果最小值是最开始的节点
        head = head->next;
    } else {
        minNode->next = minNode->next->next;
    }

    // 释放内存
    free(minNode); 

    return head;
}

// 测试函数
void printList(ListNode* head) {
    ListNode* temp = head;
    while (temp != NULL) {
        printf("%d ", temp->val);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    // 创建示例链表
    ListNode* list = malloc(sizeof(ListNode));
    list->val = 4;
    list->next = malloc(sizeof(ListNode));
    list->next->val = 2;
    list->next->next = malloc(sizeof(ListNode));
    list->next->next->val = 5;
    list->next->next->next = malloc(sizeof(ListNode));
    list->next->next->next->val = 1; // 最小值

    printf("Original List: ");
    printList(list);

    list = deleteMin(list);

    printf("List after deleting minimum: ");
    printList(list);

    return 0;
}

运行这个程序，它会删除给定链表中的最小值节点，并打印出处理后的链表。注意，在实际应用中，记得检查链表是否为空以及是否有多个最小值的情况。

试编写在带头结点的单链表中删除第一个最小值的节点的高效算法

1. 遍历单链表，找到最小值节点以及其前继节点。
2. 删除最小值节点，更新前继节点的指针。
3. 注意处理头结点的情况。

具体实现如下：

void deleteFirstMin(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        return; // 空链表或只有头结点，直接返回
    }
    Node* prev = head;
    Node* cur = head->next;
    Node* minPrev = prev;
    Node* minCur = cur;
    while (cur != nullptr) {
        if (cur->data < minCur->data) {
            minPrev = prev;
            minCur = cur;
        }
        prev = cur;
        cur = cur->next;
    }
    if (minCur == head->next) {
        // 第一个节点就是最小值节点，直接删除
        head->next = minCur->next;
        delete minCur;
    } else {
        // 删除最小值节点
        minPrev->next = minCur->next;
        delete minCur;
    }
}