AB16-删除带头结点单链表中唯一的最小值结点

代码实现

/**
 * 删除带头结点单链表中唯一的最小值结点
 * @param L 指向链表头结点的指针
 */
void del_min(LinkList L) {
    // 边界条件检查：空链表或只有一个头结点
    if (L == NULL || L->next == NULL) {
        return;  // 无需删除
    }

    // p指向当前结点的前驱结点（从头结点开始）
    LNode p = L;

    // 指向最小值结点的前驱结点
    LNode pre_min = L;

    // 遍历链表查找最小值结点
    while (p->next != NULL) {
        // 如果当前结点的值小于已知最小值
        if (p->next->data < pre_min->next->data) {
            pre_min = p;  // 更新最小值结点的前驱
        }
        p = p->next;  // 继续向后查找
    }

    // 找到最小值结点u
    LNode temp = pre_min->next;

    // 删除操作：绕过最小值结点
    pre_min->next = temp->next;  // 前驱结点指向最小值结点的后继

    // 释放最小值结点的内存
    free(temp);
}

算法执行流程图解

查找最小值过程：

链表：L→[ ]→[5]→[2]→[8]→[3]→[7]→NULL

初始化：
p=L, pos=L
p->next=[5], pos->next=[5]

查找过程：
1. p=[5]: p->next=[2], 2<5? 是 → pos=[5]
   p=[2]: p->next=[8], 8<2? 否
   p=[8]: p->next=[3], 3<2? 否
   p=[3]: p->next=[7], 7<2? 否
   p=[7]: p->next=NULL, 结束

最终：pos指向[5]，最小值结点[2]是pos->next

删除操作图解：

删除前：
L→[ ]→[5]→[2]→[8]→[3]→[7]→NULL
     ↑    ↑    ↑
    pos   u   u->next

删除操作：
1. pos->next = u->next
   L→[ ]→[5]→[8]→[3]→[7]→NULL
     ↑         ↑
    pos      u->next

2. free(u)
   L→[ ]→[5]→[8]→[3]→[7]→NULL

复杂度分析

时间复杂度：O(n)

• 查找时间：需要遍历整个链表一次，O(n)
• 删除时间：常数时间O(1)
• 总体时间复杂度：O(n)

空间复杂度：O(1)

• 额外空间：只使用了常数个指针变量：p、pos、u
• 无辅助空间：没有使用额外的数据结构
• 算法额外空间复杂度：O(1)

优化版本1：更清晰的逻辑和变量命名

/**
 * 优化版本1：更清晰的逻辑和变量命名
 */
void del_min_Optimized1(LinkList L) {
    // 边界检查
    if (L == NULL || L->next == NULL) {
        return;
    }

    // current指向当前结点的前驱
    LinkList current = L;

    // min_prev指向最小值结点的前驱
    LinkList min_prev = L;

    // 遍历链表查找最小值结点
    while (current->next != NULL) {
        if (current->next->data < min_prev->next->data) {
            min_prev = current;
        }
        current = current->next;
    }

    // 执行删除
    LinkList min_node = min_prev->next;
    min_prev->next = min_node->next;
    free(min_node);
}

优化版本2：返回被删除的最小值

/**
 * 优化版本2：返回被删除的最小值
 */
int del_min_with_return(LinkList L) {
    if (L == NULL || L->next == NULL) {
        return INT_MIN;  // 返回错误值
    }

    LinkList p = L;
    LinkList pos = L;

    while (p->next != NULL) {
        if (p->next->data < pos->next->data) {
            pos = p;
        }
        p = p->next;
    }

    LinkList u = pos->next;
    int min_value = u->data;
    pos->next = u->next;
    free(u);

    return min_value;
}

算法特点

核心思想： 1. 单次遍历：通过一次遍历找到最小值结点 2. 前驱指针：使用前驱指针技术，便于删除操作 3. 原地删除：直接修改指针连接，不使用额外空间

关键技巧： - 双指针技术：p用于遍历，pos记录最小值前驱 - 比较策略：比较p->next->data和pos->next->data - 删除时机：遍历结束后立即删除

算法正确性证明： 1. 初始化：pos和p都从头结点开始 2. 循环不变式：在每次循环开始时，pos->next始终指向当前已知的最小值结点 3. 终止条件：当p->next == NULL时，已遍历完整个链表 4. 结果正确：pos->next指向全局最小值结点

易错点分析： 1. 初始条件：pos必须初始化为L，而不是L->next 2. 比较对象：比较的是p->next->data而不是p->data 3. 指针更新：只有找到更小值时才更新pos

这种算法效率很高，只需要一次遍历就能完成查找和删除操作，是链表操作中的经典算法。