147. 对链表进行插入排序
题目描述
输入单链表的头节点 head。用插入排序把链表按节点值从小到大排列，返回排序后的头节点。
插入排序的做法：维护一个已排好序的部分，初始只含第一个节点。每轮从剩余部分取出一个节点，在已排好的部分中找到它应在的位置并插进去。所有节点都插完后排序结束。
链表用数组表示，例如 [1,2,3]。
示例 1
输入：head = [4,2,1,3] 输出：[1,2,3,4]
解释：依次插入 2、1、3 后得到 [1,2,3,4]。
示例 2
输入：head = [-1,5,3,4,0] 输出：[-1,0,3,4,5]
解释：排序后为 [-1,0,3,4,5]。
数据范围
- 节点数在
[1, 5000]之间。 -5000 <= Node.val <= 5000
解题思路
用一个哑节点 dummy 挂一条“已排序链表”，开始为空。每次从原链表摘下一个节点 cur：先用 nxt 记住它的后继，再让 prev 从 dummy 出发向后走，停在第一个“下一个值不小于 cur.val”的位置，把 cur 接到 prev 后面。哑节点让“插到最前面”和“插到中间”写法完全一样。
为什么正确
每轮开始时，dummy.next 起的链是已处理节点的升序排列；nxt 起的链是尚未处理的原始顺序。
复杂度分析
时间 O(n^2)（每次插入最多扫描整条已排序链），额外空间 O(1)。
易错点
改 cur.next 之前必须先保存 nxt = cur.next，否则剩下的原链表就丢了。比较要用 prev.next.val < cur.val（看下一个），而不是 prev.val。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0)
cur = head
while cur:
nxt = cur.next
prev = dummy
while prev.next and prev.next.val < cur.val:
prev = prev.next
cur.next = prev.next
prev.next = cur
cur = nxt
return dummy.nextclass Solution {
public ListNode insertionSortList(ListNode head) {
ListNode dummy = new ListNode(0);
ListNode cur = head;
while (cur != null) {
ListNode nxt = cur.next;
ListNode prev = dummy;
while (prev.next != null && prev.next.val < cur.val) {
prev = prev.next;
}
cur.next = prev.next;
prev.next = cur;
cur = nxt;
}
return dummy.next;
}
}class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
ListNode* dummy = new ListNode(0);
ListNode* cur = head;
while (cur) {
ListNode* nxt = cur->next;
ListNode* prev = dummy;
while (prev->next && prev->next->val < cur->val) {
prev = prev->next;
}
cur->next = prev->next;
prev->next = cur;
cur = nxt;
}
return dummy->next;
}
};func insertionSortList(head *ListNode) *ListNode {
dummy := &ListNode{Val: 0}
cur := head
for cur != nil {
nxt := cur.Next
prev := dummy
for prev.Next != nil && prev.Next.Val < cur.Val {
prev = prev.Next
}
cur.Next = prev.Next
prev.Next = cur
cur = nxt
}
return dummy.Next
}var insertionSortList = function(head) {
const dummy = new ListNode(0);
let cur = head;
while (cur) {
const nxt = cur.next;
let prev = dummy;
while (prev.next && prev.next.val < cur.val) {
prev = prev.next;
}
cur.next = prev.next;
prev.next = cur;
cur = nxt;
}
return dummy.next;
};function insertionSortList(head: ListNode | null): ListNode | null {
const dummy = new ListNode(0);
let cur = head;
while (cur) {
const nxt = cur.next;
let prev = dummy;
while (prev.next && prev.next.val < cur.val) {
prev = prev.next;
}
cur.next = prev.next;
prev.next = cur;
cur = nxt;
}
return dummy.next;
}