C++实现链表插入排序

算法原理与思路

链表插入排序的核心思想与数组插入排序类似，通过维护一个已排序部分和一个待处理部分，将待处理节点逐个插入到已排序部分的正确位置。在链表操作中，直接使用虚拟节点（dummy node）作为已排序链表的头部可以极大简化边界条件的处理，无需频繁修改头指针。

C++代码实现

以下是基于C++的标准实现。主要逻辑包括：

• dummy：创建一个值为-1的头指针，指向排序后的新链表。
• cur：用于在已排序链表中寻找当前节点应该插入的位置。
• head：遍历原始链表中的节点。

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode *dummy = new ListNode(-1), *cur = dummy;
        while (head) {
            ListNode *t = head->next;
            cur = dummy;
            while (cur->next && cur->next->val <= head->val) {
                cur = cur->next;
            }
            head->next = cur->next;
            cur->next = head;
            head = t;
        }
        return dummy->next;
    }
};

执行过程解析

1. 初始化阶段：创建 dummy 节点和游标 cur，此时未排序的链表由 head 指向。
2. 保存后继：在移动 head 节点前，必须先用临时指针 t 保存其下一个节点，防止断链后无法继续遍历。
3. 寻找插入位：while 循环从 dummy 开始遍历已排序部分，找到第一个大于当前 head->val 的前驱节点，即目标位置的 cur。
4. 执行插入：将 head 摘除并插入到 cur 之后。

结果与性能评估

该方法的时间复杂度取决于内层查找循环的次数，总体平均和最坏情况均为 $O(n^2)$，但在最好情况下（输入已经有序）可以达到 $O(n)$。其最显著的优势在于空间复杂度为 $O(1)$，仅使用了常数个额外指针变量，非常适合内存受限的环境。

以上就是C++实现LeetCode(147.链表插入排序)的详细内容，更多关于C++实现链表插入排序的资料请关注本站其它相关文章！