LeetCode 147. 对链表进行插入排序

2026-08-28 HGNULB 约 5 分钟

文章信息 9 个分类 3 个标签

分类

题目描述

✅ 147. 对链表进行插入排序

题意分析

输入是一个单链表的头节点，要求把它按节点值升序重排，返回新的头节点。题目额外限定了排序方式，这不是「随便怎么排都行」的题，而是指定了做法再考实现细节。

单链表的特性决定了实现形态：不能按下标随机访问，第 k 个节点必须从头走 k 步；但只要拿到某个节点的前驱，插入和删除都是常数时间的指针改写。所以数组里「腾位置搬元素」的动作在这里被「改两根指针」取代。

约束里节点数不超过 5000，节点值可以是负数。规模刚好允许平方级做法通过，也从侧面印证了题目预期的就是逐个插入的写法。

边界上要覆盖：空链表直接返回空；只有一个节点时原样返回；输入已经有序时不应该被打乱；出现相等值时要保证不会因为比较符号写错而丢节点或死循环。头节点会因为排序而改变，所以不能假设返回值还是原来的 head。

解法：哑节点维护已排序链表

核心思路

链表不能像数组那样向右搬移元素，但可以摘下一个节点，再把它插入已排序区间。用 lastSorted 表示已排序前缀的尾节点，cur = lastSorted.next 是下一个待处理节点。

循环不变量是：每轮开始时，从 head 到 lastSorted 已按非递减顺序排好，lastSorted 之后仍是尚未处理的节点。

若 lastSorted.val <= cur.val，cur 本就在正确位置，只需扩展已排序前缀。否则从哑节点 dummy 开始找插入前驱 pre，使 pre.next 是第一个严格大于 cur.val 的节点；先用 lastSorted.next = cur.next 摘下 cur，再将它插到 pre 之后。

哑节点让插到链头也无需特判；查找条件使用 <=，会让后出现的相等节点保持在先出现节点之后，因而排序稳定。

解题步骤

空链表直接返回；否则创建 dummy -> head，并令 lastSorted = head。

只要 lastSorted.next 非空，就令 cur = lastSorted.next 处理它。

若 lastSorted.val <= cur.val，前缀仍有序，直接令 lastSorted = cur。

否则从 dummy 开始找插入前驱 pre，使 pre.next.val > cur.val。

按「摘下 cur → cur 接上插入点后半段 → pre 接上 cur」的顺序改写三根指针。

循环结束后返回 dummy.next。

以 4 -> 2 -> 1 -> 3 为例：初始有序前缀是 [4]；将 2 和 1 依次插到链头，得到 1 -> 2 -> 4 -> 3；再将 3 插到 2 与 4 之间，得到 1 -> 2 -> 3 -> 4。

代码实现

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode dummy = new ListNode(0, head);
        ListNode lastSorted = head;
        while (lastSorted.next != null) {
            ListNode cur = lastSorted.next;
            if (lastSorted.val <= cur.val) {
                lastSorted = cur;
                continue;
            }

            ListNode pre = dummy;
            while (pre.next.val <= cur.val) {
                pre = pre.next;
            }

            lastSorted.next = cur.next;
            cur.next = pre.next;
            pre.next = cur;
        }
        return dummy.next;
    }
}

func insertionSortList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }

    dummy := &ListNode{Next: head}
    lastSorted := head
    for lastSorted.Next != nil {
        cur := lastSorted.Next
        if lastSorted.Val <= cur.Val {
            lastSorted = cur
            continue
        }

        pre := dummy
        for pre.Next.Val <= cur.Val {
            pre = pre.Next
        }

        lastSorted.Next = cur.Next
        cur.Next = pre.Next
        pre.Next = cur
    }
    return dummy.Next
}

复杂度分析

时间复杂度：最坏 $O(n^2)$，逆序等情况下，每个待插节点都要线性查找位置；已升序时每轮只做一次比较，最好为 $O(n)$。

空间复杂度：$O(1)$，只使用哑节点和若干指针，节点均在原链表上重连。

关键点总结

lastSorted 把链表划分为已排序前缀和未处理后缀，循环只处理边界后的第一个节点。

当 cur 不小于有序前缀的尾值时无需查找和重连，这使已有序输入降为 $O(n)$。

哑节点统一了链头和中间插入；三步重连的顺序是「摘下、接后缀、接前驱」。

查找时跳过 <= cur.val 的节点可保持稳定性；若不再限定插入排序且要求 $O(n \log n)$，应改用链表归并排序。

易错点总结

不先处理空链表就访问 head.next，会空指针异常。

摘下 cur 时误写成 lastSorted = cur.next：需要改的是 lastSorted.next，有序前缀的尾节点本身不能移动。

先执行 pre.next = cur 再读取原来的 pre.next，会让 cur.next 指向自己形成环；必须先保存后半段。

每轮插入后执行 lastSorted = cur：cur 被移到前面，不再是已排序前缀的尾，此时 lastSorted 应留在原位。

查找时用 < 而不是 <=，排序数值仍正确，但相等节点的原始先后次序会被颠倒，不再稳定。

返回 head 而不是 dummy.next：最小节点移到链头后，原 head 已不再是结果起点。

相似题目

题目	难度	考察点
148. 排序链表	中等	同样是链表排序但要求 $O(n \log n)$，用归并加快慢指针找中点
21. 合并两个有序链表	简单	双链归并的基本功，是链表归并排序的合并步骤
86. 分隔链表	中等	按阈值拆成两条链再拼接，考察双哑节点的用法
328. 奇偶链表	中等	按下标奇偶重排，需要交替推进两条链的尾指针
912. 排序数组	中等	数组版排序模板，对照体会随机访问带来的差异