0147. Insertion Sort List¶
题目信息¶
- 题号:
对链表进行插入排序
- 难度:
Medium
- 主题:
链表、插入排序、有序前缀、指针重连
- 原题:
- 重点:
维护有序前缀与未处理后缀的边界,只移动逆序节点,并按摘除后再插入的顺序保持链不断裂
题目重述¶
给定单链表 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->next 可达,没有节点复制、释放或遗漏。插入目标位于已断开位置之前,指针只连向前缀原后继,
不会形成环。
公开入口采用有序前缀版本。最坏逆序输入中,第 i 个节点仍可能扫描 O(i) 前缀,总时间
O(n^2);已排序输入只需 O(n)。工作空间为哨兵和固定指针,O(1)。重建版保留为插入排序定义的
直接基线,优化版删除了已在正确位置节点的重复查找。