0147. Insertion Sort List

题目信息

题号:
  1. 对链表进行插入排序

难度:

Medium

主题:

链表、插入排序、有序前缀、指针重连

原题:

LeetCode 0147

重点:

维护有序前缀与未处理后缀的边界,只移动逆序节点,并按摘除后再插入的顺序保持链不断裂

题目重述

给定单链表 head,使用插入排序把节点按 val 非递减排列,并返回排序后头节点。按插入排序过程,依次 取出下一个未处理节点,插入此前已经排好序的部分。结果必须保留全部原节点;相同值节点也不能丢失。

自建示例

  • 6 -> 1 -> 4 -> 1 -> 3 排序为 1 -> 1 -> 3 -> 4 -> 6;后出现的第二个 1 插在 先出现的 1 之后,可保持稳定顺序;

  • -2 -> 5 -> 0 -> -4 排序为 -4 -> -2 -> 0 -> 5;

  • 已有序链 1 -> 2 -> 3 不需要移动任何节点;空链返回空。

C++ 实现

class Solution {
private:
    ListNode* rebuildByInsertion(ListNode* head) {
        ListNode sentinel(0);

        while (head != nullptr) {
            ListNode* current = head;
            head = head->next;

            ListNode* insertionPrevious = &sentinel;
            while (insertionPrevious->next != nullptr &&
                   insertionPrevious->next->val <= current->val) {
                insertionPrevious = insertionPrevious->next;
            }
            current->next = insertionPrevious->next;
            insertionPrevious->next = current;
        }
        return sentinel.next;
    }

    ListNode* maintainSortedPrefix(ListNode* head) {
        if (head == nullptr) {
            return nullptr;
        }

        ListNode sentinel(0);
        sentinel.next = head;
        ListNode* sortedTail = head;
        ListNode* current = head->next;

        while (current != nullptr) {
            if (sortedTail->val <= current->val) {
                sortedTail = current;
            } else {
                ListNode* insertionPrevious = &sentinel;
                while (insertionPrevious->next != current &&
                       insertionPrevious->next->val <= current->val) {
                    insertionPrevious = insertionPrevious->next;
                }

                sortedTail->next = current->next;
                current->next = insertionPrevious->next;
                insertionPrevious->next = current;
            }
            current = sortedTail->next;
        }
        return sentinel.next;
    }

public:
    ListNode* insertionSortList(ListNode* head) {
        return maintainSortedPrefix(head);
    }
};

题解

把数组插入排序翻译成链表动作

插入排序的核心不变量是:处理第 i 个元素前,前 i 个元素已经有序;随后把当前元素放入这个有序段 的正确位置。数组需要右移一段元素腾出位置,链表则只需找到插入点并修改指针,不需要搬动节点值。

最直接的 rebuildByInsertion 建立一条初始为空的有序链。每轮先从输入头取下一个 current,再从 哨兵开始寻找第一个值大于它的节点,插到该节点之前。处理过的节点全部在新链,未处理节点由 head 保持,状态分界清楚。

这个方案每个节点都重新扫描插入位置。即使输入本来已有很长的有序前缀,后一个节点已经位于正确末尾,仍 会从哨兵走完整个前缀。最坏时间是 O(n^2),而有序输入也做近似同样多的查找。

结构信息:原链前缀本来就可能已经有序

无需把所有节点搬到另一条链。维护 sentinel.next 到 sortedTail 为已排序前缀,令 current = sortedTail->next 为下一个未处理节点,其后仍保持原输入顺序。

若 sortedTail->val <= current->val,因为 sortedTail 已是前缀最大值,current 也不小于它, 当前位置就是有序前缀末尾;只把 sortedTail 前进一步即可,不做查找或重连。这个快速分支让已排序输入 降为线性扫描。

逆序节点的摘除与插入

若 current->val < sortedTail->val,当前位置破坏有序性,才从哨兵查找插入点。循环越过所有 value <= current->val 的已有节点,停在第一个更大值之前。随后三次赋值分两阶段:

sortedTail->next = current->next       摘除 current,接回未处理后缀
current->next = insertionPrevious->next
insertionPrevious->next = current      插入有序前缀

第一行必须在覆盖 current->next 之前执行,否则未处理后继会丢失。插入后 sortedTail 仍是有序前缀 末尾;被移动的 current 已放到它之前,所以下一未处理节点固定是新的 sortedTail->next。代码统一在 轮末从这里取得下一状态,而不是沿已移动节点的 next 前进。

哨兵节点解决什么边界

当前节点可能小于所有已有值,需要插到真实头节点之前。栈上的 sentinel 提供固定前驱,使“头插”和 “中间插入”都使用同一组指针操作;它不是返回链的一部分,函数返回 sentinel.next。哨兵值为零没有 排序含义,查找只比较它的后继。

查找条件中的 insertionPrevious->next != current 给有序前缀设置明确右边界,避免扫描进入未处理区。 在逆序分支中至少 sortedTail 的值大于当前值,实际一定会在前缀内停止;边界条件仍让代码的不变量更 直接,也避免无条件解引用越界。

相等值与稳定性

查找时使用 <=,会越过前缀中所有与 current 相等的节点,再把后出现的当前节点插在它们之后, 保持相同值的原相对顺序。若使用 <,当前节点会插到已有同值节点之前,数值排序仍正确,但不再稳定。

对 6 -> 1 -> 4 -> 1 -> 3 的核心状态:

当前节点

排序前缀变化

sortedTail

1

从 6 后摘下,插到头部,得到 1, 6

仍为 6

4

插入 1 与 6 之间,得到 1, 4, 6

仍为 6

第二个 1

越过第一个 1 后插入,得到 1, 1, 4, 6

仍为 6

3

插到两个 1 之后、4 之前

仍为 6,后缀为空

节点完整性与复杂度

每轮要么只扩张前缀,要么先把一个现有节点从边界后摘下再插入前缀;未处理后缀始终由 sortedTail->next 可达,没有节点复制、释放或遗漏。插入目标位于已断开位置之前,指针只连向前缀原后继, 不会形成环。

公开入口采用有序前缀版本。最坏逆序输入中,第 i 个节点仍可能扫描 O(i) 前缀,总时间 O(n^2);已排序输入只需 O(n)。工作空间为哨兵和固定指针,O(1)。重建版保留为插入排序定义的 直接基线,优化版删除了已在正确位置节点的重复查找。