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

约 5 分钟
文章信息 9 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节 美团 京东 滴滴
标签
排序 链表

题目描述

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

image-20260928235309100

image-20260928235309101

image-20260928235309102

题意分析

按插入排序将链表排成非递减顺序：每次取出一个尚未处理的节点，插入已经有序的部分。链表可以通过重连指针完成插入，无需移动其他节点的值；主要工作是从前往后寻找插入位置。

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

核心思路

[!blue]

在链表前放一个哑节点 dummy，用 lastSorted 指向已排序前缀的尾部。循环开始时，从 dummy.next 到 lastSorted 始终有序，待处理节点就是紧随其后的 cur = lastSorted.next。

lastSorted 已是前缀最大值。若 cur.val >= lastSorted.val，把 cur 直接纳入前缀即可，只需让 lastSorted 前进。否则从 dummy 开始寻找插入前驱 pre，跳过所有值不大于 cur.val 的节点，停在第一个更大值之前。此时把 cur 插进去，前缀仍保持有序。

查找一定能在有序前缀内停止：进入这个分支时，已经知道 lastSorted.val > cur.val，所以最迟会在 lastSorted 之前找到位置，不会走到未处理后缀或空节点。跳过相等值再插入，也保证相同值节点的原有顺序不变。

重连时先用 lastSorted.next = cur.next 摘下 cur，保住未处理后缀；再令 cur.next = pre.next 接住插入点之后的链；最后令 pre.next = cur 完成插入。cur 被移到前面后，原 lastSorted 仍是有序尾，无需移动。每轮恰好将一个节点纳入有序前缀，直到没有待处理节点，整个链表就已排好序。

解题步骤

  • 空链表直接返回；否则创建 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，它始终指向排序后的链头。单节点链表无需进入循环，直接返回原节点。

代码实现

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)$。共处理 $n-1$ 个节点，每次查找最多遍历当前有序前缀，累计可能达到 $O(1+2+\cdots+n)$。已升序时每轮直接扩展前缀，逆序时每轮直接插到头部，这两种情况都只需 $O(n)$。
  • 空间复杂度：$O(1)$，只使用哑节点和若干指针，节点均在原链表上重连。

关键点总结

[!green]

  • lastSorted 把链表划分为已排序前缀和未处理后缀，循环只处理边界后的第一个节点。
  • 当 cur 不小于有序前缀的尾值时无需查找和重连，这使已有序输入降为 $O(n)$。
  • 哑节点统一了链头和中间插入；三步重连的顺序是「摘下、接后缀、接前驱」。
  • 查找时跳过 <= cur.val 的节点可保持稳定性。

易错点总结

[!yellow]

  • 不先处理空链表就访问 head.next，会空指针异常。
  • 摘下 cur 时误写成 lastSorted = cur.next：需要改的是 lastSorted.next，有序前缀的尾节点本身不能移动。
  • 先执行 pre.next = cur 再读取原来的 pre.next，会让 cur.next 指向自己形成环；必须先保存后半段。
  • 每轮插入后执行 lastSorted = cur：cur 被移到前面，不再是已排序前缀的尾，此时 lastSorted 应留在原位。
  • 查找时用 < 而不是 <=，排序数值仍正确，但相等节点的原始先后次序会被颠倒，不再稳定。
  • 返回 head 而不是 dummy.next：最小节点移到链头后，原 head 已不再是结果起点。

相似题目

题目 难度 关联与区别
21. 合并两个有序链表 简单 把一个节点插入有序链可理解为单节点链与已排序链的局部合并。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/87842493
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！