AB17-按递增有序输出单链表中各结点的数值，并释放所有空间

代码实现

/**
 * 按递增有序输出单链表中各结点的数值，并释放所有空间
 * 算法思想：不断寻找最小值结点，输出后删除
 * @param L 指向链表头结点的指针
 */
void del_min(LinkList L) {
    // 边界条件检查
    if (L == NULL) {
        return;
    }

    // 循环直到链表为空（只有头结点）
    while (L->next != NULL) {
        // p指向当前结点的前驱（从头结点开始）
        LNode* p = L;

        // pos指向最小值结点的前驱结点(从头结点开始)
        LNode* pos = L;

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

        // 找到最小值结点，输出其值
        printf("%d ", pos->next->data);

        // 准备删除最小值结点
        LNode* u = pos->next;  // u指向要删除的最小值结点

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

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

    // 释放头结点
    free(L);
}

算法执行流程图解

执行过程示例

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

第1轮：
查找最小值：2
输出：2
删除后：L→[ ]→[5]→[8]→[3]→[7]→NULL

第2轮：
查找最小值：3
输出：3
删除后：L→[ ]→[5]→[8]→[7]→NULL

第3轮：
查找最小值：5
输出：5
删除后：L→[ ]→[8]→[7]→NULL

第4轮：
查找最小值：7
输出：7
删除后：L→[ ]→[8]→NULL

第5轮：
查找最小值：8
输出：8
删除后：L→[ ]→NULL

最终：释放头结点，链表完全释放

详细执行步骤图解

第1轮：查找最小值
L→[ ]→[5]→[2]→[8]→[3]→[7]→NULL
 ↑    ↑    ↑    ↑    ↑    ↑
pos  pos→next p→next...

找到最小值[2]，输出2，删除[2]

第2轮：查找最小值
L→[ ]→[5]→[8]→[3]→[7]→NULL
 ↑    ↑    ↑    ↑    ↑
pos  pos→next p→next...

找到最小值[3]，输出3，删除[3]

...以此类推

复杂度分析

时间复杂度：O(n²)

• 外层循环：执行n次（每个结点删除一次）
• 内层查找：第i次循环需要查找n-i+1个结点
• 总比较次数：n + (n-1) + (n-2) + ... + 1 = n(n+1)/2
• 总体时间复杂度：O(n²)

空间复杂度：O(1)

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

优化版本1：添加边界检查和更清晰的逻辑

/**
 * 优化版本1：添加边界检查和更清晰的逻辑
 */
void del_min_Optimized1(LinkList L) {
    if (L == NULL) return;

    while (L->next != NULL) {
        LinkList p = L;
        LinkList pos = L;

        // 查找最小值结点
        while (p->next != NULL) {
            if (p->next->data < pos->next->data) {
                pos = p;
            }
            p = p->next;
        }

        // 输出并删除最小值结点
        printf("%d ", pos->next->data);
        LinkList u = pos->next;
        pos->next = u->next;
        free(u);
    }

    free(L);
}

优化版本2：返回输出的结点个数

/**
 * 优化版本2：返回输出的结点个数
 */
int del_min_with_count(LinkList L) {
    if (L == NULL) return 0;

    int count = 0;

    while (L->next != NULL) {
        LinkList p = L;
        LinkList pos = L;

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

        printf("%d ", pos->next->data);
        LinkList u = pos->next;
        pos->next = u->next;
        free(u);
        count++;
    }

    free(L);
    return count;
}

高效版本：先排序再输出（时间复杂度O(nlogn)）

/**
 * 高效版本：先排序再输出（时间复杂度O(nlogn)）
 * 使用归并排序思想
 */
void sort_and_print(LinkList L) {
    if (L == NULL || L->next == NULL) {
        if (L) free(L);
        return;
    }

    // 将链表排序（实现省略，可用归并排序）
    LinkList sorted = merge_sort(L->next);
    free(L);  // 释放原头结点

    // 有序输出并释放
    while (sorted != NULL) {
        LinkList temp = sorted;
        printf("%d ", temp->data);
        sorted = sorted->next;
        free(temp);
    }
}

算法特点

核心思想： - 不断寻找全局最小值 - 输出后立即删除 - 重复此过程直到链表为空

关键特性： 1. 输出有序：按递增顺序输出所有元素 2. 完全释放：释放所有结点（包括头结点）的空间 3. 原地操作：不需要额外存储空间 4. 破坏性操作：原链表被完全销毁

应用场景： - 需要有序输出并释放内存的场景 - 一次性使用的临时链表处理 - 内存敏感的应用

与其他排序输出的对比：

方法	时间复杂度	空间复杂度	特点
本算法	O(n²)	O(1)	简单，但效率低
先排序	O(nlogn)	O(1)	效率高，但实现复杂
转数组	O(nlogn)	O(n)	易实现，但需额外空间

算法正确性证明

1. 循环不变式：每次循环开始时，剩余链表中的最小值是下一个要输出的值
2. 终止条件：当L->next == NULL时，所有结点都已输出和删除
3. 结果正确：由于每次输出当前最小值，所以输出序列递增有序
4. 内存安全：每个结点都被free()释放，无内存泄漏

这种算法虽然时间复杂度较高，但胜在实现简单、空间效率高，适合数据量不大的场景。