Sort List 是 LeetCode Hot 100 里面一道非常经典的链表题。
这道题的难点在于：
它不是让我们把链表转成数组以后再排序，而是要求我们直接在链表上完成排序，并且时间复杂度要尽量优秀。
如果是数组排序，我们可能很自然会想到快速排序、归并排序，或者直接调用排序函数。但放到链表里，很多数组中常见的操作就不那么方便了。
比如：
-
数组可以通过下标快速访问中间位置
-
链表不能随机访问，只能一步一步往后走
-
-
链表更适合做“拆分”和“合并”
所以这道题最适合链表的数据结构特点的方法，其实就是：
归并排序。
你给出的这份 Java 代码，正是这道题最标准、也最常见的一种写法：
快慢指针找中点 + 递归归并排序 + 合并两个有序链表
这种做法的整体思路非常清晰：
-
先用快慢指针把链表从中间断开
-
递归地把左半部分排好序
-
递归地把右半部分排好序
-
最后把两个有序链表合并起来
本文就结合这段代码，系统地讲一下这道题的解法。
一、题目描述
给你链表的头结点 head，请将其按升序排列并返回排序后的链表。
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
二、这道题为什么适合用归并排序？
很多同学一开始会想：
能不能像数组一样，直接对链表做快速排序？
理论上当然可以，但实现起来会比较麻烦，因为链表不支持随机访问，交换节点也不如数组方便。
而归并排序非常适合链表，原因有两个：
1. 链表很容易从中间拆成两段
只要用快慢指针，我们就能在线性时间内找到中点，把链表断开。
2. 两个有序链表非常容易合并
这其实就是链表的基本操作之一，只需要不断比较两个链表当前节点的值，把较小的那个接到结果链表后面即可。
所以整道题就变成了一个非常典型的“分治”问题：
-
大问题：排序整个链表
-
小问题：排序左半部分、排序右半部分
-
合并：把两个有序链表合并成一个有序链表
这就是归并排序的核心思想。
三、代码整体结构
先看你给出的代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode fast = head.next, slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode tmp = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(tmp);
ListNode h = new ListNode(0);
ListNode res = h;
while (left != null && right != null) {
if (left.val < right.val) {
h.next = left;
left = left.next;
} else {
h.next = right;
right = right.next;
}
h = h.next;
}
h.next = left != null ? left : right;
return res.next;
}
}
这段代码主要可以分成三部分：
-
递归终止条件
-
找中点并断开链表
-
合并两个有序链表
下面分别来看。
四、递归终止条件
if (head == null || head.next == null)
return head;
这一步很好理解。
如果链表为空，或者链表只有一个节点，那么它本身就已经是有序的了，不需要再继续拆分。
所以这里直接返回当前链表即可。
这也是归并排序递归结束的条件。
五、如何找到链表中点？
ListNode fast = head.next, slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
这里使用的是经典的快慢指针。
-
slow每次走一步 -
fast每次走两步
当 fast 走到链表末尾时，slow 就会停在链表的中间附近。
为什么这里是 fast = head.next？
这一点非常关键。
如果写成 fast = head，在某些偶数长度链表里，左右两部分的划分可能会不太理想。
这里让 fast 从 head.next 开始，可以让 slow 最终停在“前半段的最后一个节点”上，这样更方便我们直接断链。
例如链表：
4 -> 2 -> 1 -> 3
初始化：
-
slow = 4 -
fast = 2
循环过程：
-
第一轮后：
slow = 2，fast = 3 -
此时
fast.next == null，循环结束
最后 slow 指向值为 2 的节点，也就是前半段的最后一个节点。
六、如何把链表断成两部分？
ListNode tmp = slow.next;
slow.next = null;
这两行代码非常重要。
假设当前链表是：
4 -> 2 -> 1 -> 3
如果 slow 停在 2 这个节点，那么：
-
slow.next就是后半部分的头节点1 -
用
tmp记录这个位置 -
然后把
slow.next = null
这样链表就被真正拆成了两段：
左边：4 -> 2
右边：1 -> 3
注意，这一步一定不能少。
如果你只找中点而不把链表断开，那么递归时左右两边实际上还是连在一起的，程序就会出问题，甚至可能死递归。
七、递归排序左右两部分
ListNode left = sortList(head);
ListNode right = sortList(tmp);
这里就是归并排序里的“分治”。
-
左半部分继续递归排序
-
右半部分继续递归排序
直到每一部分都只剩一个节点或者为空时，递归结束。
这样返回上来时，左右两边就已经分别是有序链表了。
八、如何合并两个有序链表？
ListNode h = new ListNode(0);
ListNode res = h;
while (left != null && right != null) {
if (left.val < right.val) {
h.next = left;
left = left.next;
} else {
h.next = right;
right = right.next;
}
h = h.next;
}
h.next = left != null ? left : right;
return res.next;
这一部分其实就是“合并两个有序链表”的标准模板。
1. 先创建一个虚拟头节点
ListNode h = new ListNode(0);
ListNode res = h;
这里的 h 用来不断往后接节点。
res 则用来保存最终结果链表的头部位置，因为后面 h 会不断往后移动，如果不额外保存头节点，最后就找不到结果链表的起点了。
2. 比较左右链表当前节点
while (left != null && right != null) {
if (left.val < right.val) {
h.next = left;
left = left.next;
} else {
h.next = right;
right = right.next;
}
h = h.next;
}
每次从 left 和 right 当前节点中选一个较小的接到结果链表后面。
然后把对应链表的指针后移。
3. 把剩余部分直接接上
h.next = left != null ? left : right;
因为左右两边本身已经是有序链表，所以当其中一边走完以后，另一边剩下的节点一定已经有序，直接整体接到后面即可。
4. 返回结果
return res.next;
因为 res 指向的是虚拟头节点，所以真正的头节点要从 res.next 开始返回。
九、用一个例子完整模拟一下
我们以这组数据为例：
head = [4,2,1,3]
第一步：第一次拆分
原链表：
4 -> 2 -> 1 -> 3
找到中点并断开后：
左边：4 -> 2
右边：1 -> 3
第二步：递归排序左边 4 -> 2
继续拆分：
左边：4
右边：2
两个长度为 1 的链表天然有序，开始合并：
2 -> 4
第三步：递归排序右边 1 -> 3
继续拆分：
左边：1
右边：3
合并后得到：
1 -> 3
第四步：合并两个有序链表
现在左右两边分别是：
2 -> 4
1 -> 3
合并过程：
-
比较
2和1，先接1 -
比较
2和3，接2 -
比较
4和3，接3 -
最后把剩余的
4接上
最终结果：
1 -> 2 -> 3 -> 4
十、时间复杂度分析
1. 时间复杂度：O(n log n)
归并排序的时间复杂度分析和数组版本是一样的。
-
每一层递归都会遍历整条链表，把节点拆分或者合并，总成本是
O(n) -
递归层数大约是
log n
所以总时间复杂度是：
O(n log n)
这也是这道题比较理想的时间复杂度。
2. 空间复杂度：O(log n)
这份代码不是迭代版，而是递归版。
所以额外空间主要来自递归调用栈。
递归深度大约是 log n，因此空间复杂度为：
O(log n)
如果是严格要求常数级额外空间，那么通常需要写成自底向上的迭代归并排序，实现会复杂不少。
十一、这段代码的优点
你这份代码写得很简洁，而且是面试和刷题里非常经典的一版。
它的优点主要有：
1. 思路标准
这是链表排序最常见、最稳定的做法。
2. 非常符合链表特性
链表不适合随机访问，但非常适合拆分和合并，所以归并排序比快速排序更自然。
3. 代码结构清晰
整个流程就是：
-
找中点
-
断链
-
递归排序
-
合并结果
每一步都很明确，阅读成本比较低。
十二、这道题容易出错的地方
这题虽然思路标准，但细节上还是有几个常见坑。
1. 忘记断链
slow.next = null;
这一句必须有。
否则左右两部分没有真正分开，递归时会反复处理同一段链表，导致死循环或者结果错误。
2. 合并后忘记返回 res.next
因为 res 是虚拟头节点，所以最后真正返回的应该是：
return res.next;
而不是直接返回 res。
3. 快慢指针初始化不当
这里写成：
ListNode fast = head.next, slow = head;
是比较合适的。
如果写法不同，也许依然能做出来，但要特别小心偶数长度链表的划分是否正确。
十三、完整代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode fast = head.next, slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode tmp = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(tmp);
ListNode h = new ListNode(0);
ListNode res = h;
while (left != null && right != null) {
if (left.val < right.val) {
h.next = left;
left = left.next;
} else {
h.next = right;
right = right.next;
}
h = h.next;
}
h.next = left != null ? left : right;
return res.next;
}
}
十四、总结
这道 排序链表 本质上就是一道链表上的归并排序。
它最核心的思想有三点：
-
用快慢指针找到链表中点
-
递归地排序左右两部分
-
合并两个有序链表
相比数组，链表不适合随机访问，但特别适合做“拆分”和“合并”，所以归并排序几乎就是这道题最自然的解法。
如果你把这题真正理解透了，那么下面这些链表题也会更容易上手：
-
合并两个有序链表
-
合并 K 个升序链表
-
链表中点相关题目
-
链表归并排序相关扩展
这道题不只是让你学会一个排序方法，更重要的是帮助你建立一个意识：
