LeetCode 148. 排序链表

2026-09-07 HGNULB 约 7 分钟

文章信息 26 个分类 5 个标签

分类

LeetCode CodeTop 中等已解决已掌握历史考题 100-200 LeetCode 热题 100 面试经典 150 题腾讯字节阿里华为微软美团拼多多百度网易小红书快手滴滴携程 B站虾皮商汤猿辅导

题目描述

✅ 148. 排序链表

题意分析

给定单链表的头节点，将全部节点按值从小到大排列，返回排序后的头节点。重复值都要保留，不能在排序时丢失或重复连接节点；空链表返回空。

基础要求是完成升序排序，进阶要求在 $O(n\log n)$ 时间和常数额外空间内完成。把节点收集到数组会占用 $O(n)$ 空间，递归归并还会占用调用栈；下面的迭代归并通过调整原节点的 next，同时满足进阶要求。

解法：自底向上归并排序

核心思路

[!blue]

链表不能按下标直接访问中间节点，但很适合合并两条有序链表：每次只比较两个头节点，接上较小的一个，剩余部分仍然有序。归并排序利用这个操作，把短的有序段逐轮合并成更长的有序段。

size 表示本轮每段的目标长度。开始时 size = 1，单个节点天然有序；每轮把相邻两段合并，得到长度至多为 2 * size 的有序段，然后将 size 翻倍。由此每一轮开始时，待合并的各段都已经有序。段长达到整条链表的长度时，只剩一个有序段，排序完成。

每轮用 current 指向尚未处理的部分，tail 指向已合并部分的尾节点。先从 current 切出 left，再切出相邻的 right，并在合并前保存下一组的起点。split 不只是找边界，还会把段尾的 next 置空，使两段真正独立，避免合并越过本组范围。

merge 每次选择两段头节点中较小的一个接到 tail 后面；两段本来都有序，因此选出的节点也是全部未合并节点中的最小值。一段耗尽后，另一段可以整体接上，再走到真实尾节点，供下一组继续连接。整轮只保证各组内部有序，组与组之间还要留给下一轮合并。

尾部不足 size 个节点也算一段；若没有右段，就直接接回左段。哨兵节点固定链表入口，使第一组与后续各组使用相同的接线流程。

解题步骤

统计节点数 length，创建指向原头节点的哨兵 dummy。

从 size = 1 开始，每轮设置 tail = dummy、current = dummy.next。

令 left = current，切出至多 size 个节点，得到右段起点 right；再从 right 切出一段，并把剩余链表的起点保存到 current。

合并 left、right，接到 tail 后面，将 tail 更新为合并后的尾节点；继续处理 current 指向的下一组。

一轮结束后将 size 翻倍。size >= length 时返回 dummy.next；空链表和单节点链表会直接跳过合并。

代码实现

class Solution {
    public ListNode sortList(ListNode head) {
        int length = 0;

        for (ListNode node = head; node != null; node = node.next) {
            length++;
        }

        ListNode dummy = new ListNode(0, head);

        for (int size = 1; size < length; size <<= 1) {
            ListNode tail = dummy;
            ListNode current = dummy.next;

            while (current != null) {
                ListNode left = current;
                ListNode right = split(left, size);

                // 合并会改变连接，先保存下一组的入口。
                current = split(right, size);
                tail = merge(left, right, tail);
            }
        }

        return dummy.next;
    }

    // 最多切出 size 个节点并返回剩余链头，长度不足时保留实际长度。
    private ListNode split(ListNode head, int size) {
        for (int i = 1; head != null && i < size; i++) {
            head = head.next;
        }

        if (head == null) {
            return null;
        }

        ListNode next = head.next;

        // 切出的段必须独立，长度不足时也保留实际节点。
        head.next = null;

        return next;
    }

    // 把两段接在给定尾节点之后，返回包含剩余后缀在内的新尾节点。
    private ListNode merge(ListNode left, ListNode right, ListNode tail) {
        while (left != null && right != null) {
            if (left.val <= right.val) {
                tail.next = left;
                left = left.next;
            } else {
                tail.next = right;
                right = right.next;
            }

            tail = tail.next;
        }

        tail.next = left != null ? left : right;

        // 接完剩余部分后走到真实段尾，供下一组继续接入。
        while (tail.next != null) {
            tail = tail.next;
        }

        return tail;
    }
}

func sortList(head *ListNode) *ListNode {
    length := 0
    for node := head; node != nil; node = node.Next {
        length++
    }

    dummy := &ListNode{Next: head}
    for size := 1; size < length; size <<= 1 {
        tail := dummy
        current := dummy.Next

        for current != nil {
            left := current
            right := splitList(left, size)
            // 合并会改变连接，先保存下一组的入口。
            current = splitList(right, size)
            tail = mergeSortedLists(left, right, tail)
        }
    }
    return dummy.Next
}

// 最多切出 size 个节点并返回剩余链头，长度不足时保留实际长度。
func splitList(head *ListNode, size int) *ListNode {
    for i := 1; head != nil && i < size; i++ {
        head = head.Next
    }
    if head == nil {
        return nil
    }

    next := head.Next
    // 切出的段必须独立，长度不足时也保留实际节点。
    head.Next = nil
    return next
}

// 把两段接在给定尾节点之后，返回包含剩余后缀在内的新尾节点。
func mergeSortedLists(left, right, tail *ListNode) *ListNode {
    for left != nil && right != nil {
        if left.Val <= right.Val {
            tail.Next = left
            left = left.Next
        } else {
            tail.Next = right
            right = right.Next
        }
        tail = tail.Next
    }
    if left != nil {
        tail.Next = left
    } else {
        tail.Next = right
    }
    // 接完剩余部分后走到真实段尾，供下一组继续接入。
    for tail.Next != nil {
        tail = tail.Next
    }
    return tail
}

复杂度分析

时间复杂度：$O(n\log n)$。统计长度为 $O(n)$；每轮切分、合并以及走到段尾，合计只会把各节点扫描常数次，因此一轮为 $O(n)$。段长每轮翻倍，共有 $O(\log n)$ 轮。

空间复杂度：$O(1)$。复用原链表节点，只增加一个哨兵和固定数量的指针；没有数组，也没有递归调用栈。

关键点总结

[!green]

每轮开始时，各个长度至多为 size 的段已经有序，合并后将有序段长度翻倍。

切段负责划清边界，归并负责段内排序，tail 负责把各组重新串成完整链表。

先保存下一组入口，再改变本组连接，才能保住尚未处理的节点。

自底向上的迭代顺序省掉递归栈，满足常数额外空间要求。

易错点总结

[!yellow]

split 找到段尾后没有断链，两段仍互相连接，归并会重复接入节点，甚至形成环。

合并前没有保存下一组入口，原连接改变后就可能找不到剩余链表。

接上未耗尽的一段后，没有继续走到真实尾节点，下一组会覆盖仍在本组中的连接。

假定每组都有两个完整的 size 长段，会漏掉末尾的短段；切分和合并都必须允许空右段。

递归归并的时间同样是 $O(n\log n)$，但调用栈为 $O(\log n)$，不能把它写成严格的常数额外空间。

相似题目

题目	难度	关联与区别
21. 合并两个有序链表	简单	排序的合并阶段复用两条有序链表归并，分治再负责把原链表拆成更小段。
23. 合并 K 个升序链表	困难	按有序头节点逐步拼接链表；本题以归并排序反复合并子链表，该题用小顶堆或分治扩展到多条链表。
补充题 123. 双向链表的常数空间排序	中等	都按段长翻倍进行自底向上归并；补充题还要维护双向指针并控制辅助空间。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/56342791

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！