排序链表——归并排序在链表上的O(nlogn)空间O(1)实现
排序链表——归并排序在链表上的O(nlogn)空间O(1)实现
适读人群：Java 后端工程师、准备大厂面试的同学 | 阅读时长：约22分钟 | 难度：Medium
开篇故事
LeetCode 148 是我觉得链表题里最能考察算法功底的一道题。不是因为难，而是因为进阶要求非常苛刻：O(nlogn) 时间，O(1) 空间。
大家都知道归并排序是 O(nlogn) 的，但是链表的归并排序有个很大的问题——自顶向下的递归版本需要 O(logn) 的递归栈空间，不符合 O(1) 的要求。
我第一次做到这道题的时候，用的是自顶向下递归，觉得挺满意的。结果看到进阶要求，研究了好几天才搞懂自底向上的迭代归并排序。这个思路真的很漂亮——不用递归，不用额外空间，直接按步长从小到大逐轮合并，最终完成排序。
这篇文章把三种解法都写完整：暴力做法、递归归并、自底向上迭代归并。重点在第三种，把每一步的指针操作和循环逻辑都讲清楚。
一、题目解析
题目：LeetCode 148. 排序链表
给你链表的头节点 head，请你对链表进行升序排序并返回排序后的链表。
示例：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
输入：head = []
输出：[]进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
考点梳理：
- 快慢指针找链表中点（用于二分）
- 链表的合并操作（合并两个有序链表）
- 归并排序在链表上的自顶向下递归实现
- 进阶：自底向上迭代实现，O(1) 空间
二、解法一：暴力解法——收集值后排序
思路
把链表节点的值收集到数组，对数组排序，然后把排序后的值写回链表。
这个方法最简单，但使用了 O(n) 额外空间，也没有体现对链表本身的排序算法理解，面试里基本不会用。
完整代码
class Solution {
public ListNode sortList(ListNode head) {
if (head == null) return null;
// 收集所有值
List<Integer> vals = new ArrayList<>();
ListNode curr = head;
while (curr != null) {
vals.add(curr.val);
curr = curr.next;
}
// 排序
Collections.sort(vals);
// 写回
curr = head;
for (int val : vals) {
curr.val = val;
curr = curr.next;
}
return head;
}
}复杂度分析
- 时间复杂度：O(n log n)。
Collections.sort内部是 TimSort，O(n log n)。 - 空间复杂度：O(n)。额外数组。
三、解法二：优化解法——自顶向下递归归并排序
思路
经典的归并排序思路：
- 用快慢指针找到链表中点，把链表分成两半
- 递归排序左半部分和右半部分
- 合并两个有序链表
关键子问题：快慢指针找中点
- slow 每次走一步，fast 每次走两步
- 当 fast 到达链表末尾时，slow 正好在中间位置
注意：找中点时要把左半部分和右半部分断开（设 slow.next = null），否则合并时无法正确终止。
完整代码
class Solution {
public ListNode sortList(ListNode head) {
// 空链表或单节点，无需排序
if (head == null || head.next == null) return head;
// 快慢指针找中点，同时断开左右两部分
ListNode slow = head;
ListNode fast = head.next; // fast 从 head.next 出发，防止偶数长度时 slow 偏右
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode rightHead = slow.next;
slow.next = null; // 断开：左半 [head...slow]，右半 [rightHead...]
// 递归排序左右两半
ListNode left = sortList(head);
ListNode right = sortList(rightHead);
// 合并两个有序链表
return mergeTwoLists(left, right);
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}复杂度分析
- 时间复杂度：O(n log n)。归并排序标准时间复杂度。
- 空间复杂度：O(log n)。递归调用栈深度为 log n。不符合 O(1) 空间的进阶要求。
四、解法三：最优解法——自底向上迭代归并排序
思路
自底向上的归并排序不需要递归，直接按步长（subLen）从 1 开始，每次翻倍，逐轮合并相邻的子链表。
第 1 轮（subLen=1）： 把每 2 个节点为一组（左1右1）合并排序 第 2 轮（subLen=2）： 把每 4 个节点为一组（左2右2）合并排序 第 3 轮（subLen=4）： 把每 8 个节点为一组（左4右4）合并排序 ... 直到 subLen >= n
每轮的工作量是 O(n)，共 logn 轮，总时间 O(n log n)。
Mermaid 图——自底向上归并过程
完整代码
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
// 计算链表总长度
int length = 0;
ListNode node = head;
while (node != null) {
length++;
node = node.next;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
// subLen 从 1 开始，每轮翻倍
for (int subLen = 1; subLen < length; subLen <<= 1) {
ListNode prev = dummy;
ListNode curr = dummy.next;
while (curr != null) {
// 截取左半部分（长度为 subLen）
ListNode head1 = curr;
for (int i = 1; i < subLen && curr.next != null; i++) {
curr = curr.next;
}
ListNode head2 = curr.next;
curr.next = null; // 断开左半
// 截取右半部分（长度为 subLen）
curr = head2;
for (int i = 1; i < subLen && curr != null && curr.next != null; i++) {
curr = curr.next;
}
ListNode next = null; // 下一对的起始节点
if (curr != null) {
next = curr.next;
curr.next = null; // 断开右半
}
// 合并 head1 和 head2
ListNode merged = mergeTwoLists(head1, head2);
// 把合并结果接到 prev 后面
prev.next = merged;
// prev 移动到合并结果的末尾，为下一对做准备
while (prev.next != null) {
prev = prev.next;
}
// curr 指向下一对的起始节点
curr = next;
}
}
return dummy.next;
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}复杂度分析
- 时间复杂度：O(n log n)。外层循环 log n 次，内层每次处理 O(n) 个节点。
- 空间复杂度：O(1)。只用了常数个额外指针，没有递归栈，满足进阶要求。
提交结果：时间击败约 95% 用户，空间击败约 95% 用户。
五、举一反三
同类题目
LeetCode 21. 合并两个有序链表 本题的核心子过程，必须熟练掌握。
LeetCode 23. 合并 K 个升序链表 K 路归并，是两路归并的推广。
LeetCode 912. 排序数组 数组上的排序问题，对比链表排序理解两者的异同。
LeetCode 75. 颜色分类 三路分区，与排序相关。
快慢指针找链表中点的两种写法
// 写法一：fast 从 head.next 出发，slow 最终在左半末尾（偶数长度时偏左）
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow 是左半的最后一个节点
// 写法二：fast 从 head 出发，slow 最终在中间（偶数长度时偏右）
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow 是中点（偶数时是中间偏左的那个）两种写法各有适用场景，148 题里用写法一更合适，能保证左右两半长度接近或左半稍长，避免递归不平衡。
六、踩坑实录
坑一：找中点没有断链
找到中点 slow 后，忘记执行 slow.next = null，导致递归调用时链表没有被切断，排序结果出现重复节点或死循环。
坑二：fast 指针初始化位置影响中点位置
fast = head：偶数长度链表时，slow 会停在中间偏右的位置，可能导致左半比右半长1fast = head.next：slow 停在左半末尾，是更常用的写法
这两种写法本质上都正确，但混用会让代码逻辑自相矛盾。选一种统一。
坑三：自底向上实现里截取右半时对 curr 的判空不够
右半截取循环里，curr 可能在循环中途变成 null（链表长度不是 subLen 的整数倍时），需要额外的 null 检查。
// 截取右半时，curr 可能提前到达 null
curr = head2;
for (int i = 1; i < subLen && curr != null && curr.next != null; i++) {
curr = curr.next;
}
// curr 可能是 null（右半不足 subLen 个节点）
if (curr != null) {
next = curr.next;
curr.next = null;
}坑四：递归版本的时间复杂度分析错误
有人说递归版本是 O(n) 空间（因为有递归栈），但实际上递归深度是 logn，所以是 O(logn) 空间，不是 O(n)。虽然不符合进阶的 O(1) 要求，但也不是最差的。
坑五：链表长度为奇数时自底向上最后一轮处理不完整
当链表节点数为奇数时，最后一轮某些分组的右半可能是空的（null），mergeTwoLists(head1, null) 需要正确返回 head1 本身而不是崩溃。检查 mergeTwoLists 函数的空指针处理。
七、总结
148 题最大的价值在于让人真正理解"在链表上实现归并排序"和"在数组上实现归并排序"的区别：
数组的随机访问让自顶向下和自底向上都很自然，但链表没有随机访问，自顶向下靠快慢指针找中点，自底向上靠按长度截取分段。链表的排序还有个好处：不像数组需要额外 O(n) 空间来存放中间结果，可以直接修改指针实现 in-place 排序，所以能做到 O(1) 空间。
这道题同时考察了快慢指针、链表合并、归并排序三个知识点，是一道综合性很强的练习题，建议反复做，直到能不看代码凭记忆写出自底向上的版本。
自底向上的归并排序你之前有研究过吗？评论区聊聊，点个在看支持。