LeetCode 148. 排序链表

2026-09-07 HGNULB 约 6 分钟

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

分类

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

题目描述

✅ 148. 排序链表

题意分析

给定单链表的头节点 head，将链表按升序重新排列后返回新的头节点。节点数最多 5 * 10^4，节点值在 [-10^5, 10^5] 内，链表可能为空。

进阶要求是最关键的信号：$O(n \log n)$ 时间加常数级空间。时间下限排除了逐个取节点插入有序部分这类平方级做法；空间要求则堵死了「把值读进数组、排完再写回」的取巧路线——出这道题就是想看你直接在链表结构上排序。

链表与数组的本质差异是不支持按下标随机访问，只能顺序移动指针。这决定了可行的做法必须只依赖两种操作：顺序扫描，以及改接 next 指针。

边界：空链表、单节点、本就有序、所有值相等，都应正确返回。

解法：自底向上归并排序

核心思路

归并排序适合只能顺序访问的链表。依次合并长度为 1、2、4... 的相邻有序段，直到段长覆盖整条链表；全程只修改 next 指针，迭代实现不占用递归栈。

解题步骤

统计链表长度，并创建哨兵节点。

从段长 1 开始，每轮将链表切成相邻的 left、right 两段。

合并两段并接回已排序部分，同时记录下一组的起点。

段长每轮翻倍，直到不小于链表长度。

代码实现

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;
    }

    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
}

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)$ 个节点，共 $\log n$ 层。

空间复杂度：$O(1)$，只使用常数个指针并复用原节点。

关键点总结

段长按 1、2、4... 翻倍，避免递归栈并满足常数空间要求。

split 必须断开子链表，且要允许最后一段长度不足 size。

合并后返回尾节点，下一组才能直接接在其后。

节点全程复用，不创建新的结果节点。

易错点总结

切分后忘记断链，会把相邻两段重复带入合并。

合并后未更新尾节点，会覆盖上一组的连接。

漏接尚未遍历完的一段，会丢失节点。

使用递归归并会占用 $O(\log n)$ 栈空间，不满足严格的常数空间要求。

相似题目

题目	难度	考察点
21. 合并两个有序链表	简单	本题合并子过程的独立成题
23. 合并 K 个升序链表	困难	两路合并推广到 K 路的分治
147. 对链表进行插入排序	中等	平方级链表排序的对照实现
876. 链表的中间结点	简单	快慢指针找中点的独立成题
912. 排序数组	中等	数组上的手写归并与快排
LCR 077. 排序链表	中等	本题镜像题，解法完全一致
补充题 5. 手撕归并排序	中等	归并排序模板的白板默写