题目描述
思路解析
一句话答案：LeetCode 148 排序链表要求 O(n log n) 时间，标准解是归并排序：快慢指针找中点并断链，左右两半递归排好，再按「比头取小」合并两条有序链。链表版合并只改指针、不需要辅助数组，时间 O(n log n)，递归栈 O(log n)，自底向上迭代还能做到真正 O(1) 空间。
为什么链表排序首选归并排序
在 O(n log n) 的几大排序里，堆排序要按下标随机访问，链表做不到；快速排序依赖来回交换元素，链表上实现别扭且最坏会退化到 O(n²)。归并排序的两个核心动作——从中间劈开、把两条有序序列合并——恰好都是链表擅长的顺序操作。更妙的是，数组版归并需要 O(n) 辅助数组存放合并结果，链表版只需把现成节点重新接线，一个新节点都不用建，归并排序在链表上反而比在数组上更省。
快慢指针找中点，fast 为什么从 head.next 出发
找中点用快慢指针：slow 每次走一步、fast 每次走两步，fast 到尾时 slow 停在中间附近。细节在起点：fast 从 head.next 出发而不是 head，这样偶数长度时 slow 停在左半的末尾，劈出来的左半不长于右半、且两半都非空。若 fast 从 head 出发，长度为二的链会被劈成「整条加空链」，子问题规模没有变小，递归永远到不了底。
劈开之后为什么必须把链断掉
找到中点后要做两件事：记下右半的头 mid，并把左半末尾的 next 置空，也就是代码里的 slow.next = None。断链这一步最容易漏——不置空的话，左半在物理上仍然连着右半，对左半递归时快慢指针会一路跑进右半，子问题没有缩小，结果就是死循环或者栈溢出。断干净之后，左右两条子链才是彼此独立的更小问题，递归才能收敛到单节点这个天然有序的终点。
合并两条有序链为什么是对的
合并阶段用一个哨兵节点起头，反复比较两条链的头节点，把较小者摘下来接到结果尾部，某一条走完后把另一条整段接上。正确性来自两条链各自有序：两个头当中较小的那个，必然小于等于双方剩余的所有节点，把它放到结果的下一个位置不可能出错。值相等时优先取左半的节点（比较用小于等于），能让相同元素保持原有先后，也就是稳定排序。
复杂度怎么数，空间还能再省吗
每层递归把链劈成两半，共约 log n 层；每一层的全部合并加起来恰好扫 n 个节点，总时间 O(n log n)。合并不新建节点，额外开销只剩递归调用栈的 O(log n)。想做到严格 O(1) 空间，可以改成自底向上的迭代写法：先按子段长度一两两合并，再按二、四逐层翻倍，用循环替代递归，逻辑同构但不吃栈空间——这是本题最常见的面试追问。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住「拆半 → 递归 → 合并」这条主线，下面逐帧演示。
快慢指针起步：slow 指头 4，fast 指 2（从 head.next 起）。slow 每步走 1 个、fast 每步走 2 个，fast 到尾时 slow 正好停在中点。
slow 前移到 2，fast 前移两步到 1。fast 还没到尾，继续。
slow 前移到 7，fast 前移两步到 3。fast 还没到尾，继续。
在中点后断开：左半 4→2→7、右半 1→5→3。接下来对左右两半各自递归排序。
递归左半 [4,2,7]：再对半 → [4,2] 与 [7]。[7] 只剩一个节点，天然有序（标绿）。
[4,2] 再对半 → [4] 与 [2]，都到单节点。递归到底：每段只剩一个，全部天然有序。
递归右半 [1,5,3]：对半 → [1] 与 [5,3]。[1] 单节点有序。
[5,3] 再对半 → [5] 与 [3]，都到单节点。现在 6 个单节点 [4][2][7][1][5][3] 全部有序，开始一层层合并回去。
归并 4 与 2：两个指针 p、q 各指两段头，比头取小，接到结果尾。
比两段头：左 4 vs 右 2。右 2 更小，取它。
把 2 接到结果尾（绿）。从右段取走的节点标灰，该段指针前移。
右段已空，把左段剩下的整段直接接上，当前接 4。
把 4 接到结果尾（绿）。从左段取走的节点标灰，该段指针前移。
4 与 2 合成有序段 2→4。
归并 2→4 与 7：两个指针 p、q 各指两段头，比头取小，接到结果尾。
比两段头：左 2 vs 右 7。左 2 更小（相等优先取左·稳定），取它。
把 2 接到结果尾（绿）。从左段取走的节点标灰，该段指针前移。
比两段头：左 4 vs 右 7。左 4 更小（相等优先取左·稳定），取它。
把 4 接到结果尾（绿）。从左段取走的节点标灰，该段指针前移。
左段已空，把右段剩下的整段直接接上，当前接 7。
把 7 接到结果尾（绿）。从右段取走的节点标灰，该段指针前移。
2→4 与 7 合成有序段 2→4→7。
归并 5 与 3：两个指针 p、q 各指两段头，比头取小，接到结果尾。
比两段头：左 5 vs 右 3。右 3 更小，取它。
把 3 接到结果尾（绿）。从右段取走的节点标灰，该段指针前移。
右段已空，把左段剩下的整段直接接上，当前接 5。
把 5 接到结果尾（绿）。从左段取走的节点标灰，该段指针前移。
5 与 3 合成有序段 3→5。
归并 1 与 3→5：两个指针 p、q 各指两段头，比头取小，接到结果尾。
比两段头：左 1 vs 右 3。左 1 更小（相等优先取左·稳定），取它。
把 1 接到结果尾（绿）。从左段取走的节点标灰，该段指针前移。
左段已空，把右段剩下的整段直接接上，当前接 3。
把 3 接到结果尾（绿）。从右段取走的节点标灰，该段指针前移。
左段已空，把右段剩下的整段直接接上，当前接 5。
把 5 接到结果尾（绿）。从右段取走的节点标灰，该段指针前移。
1 与 3→5 合成有序段 1→3→5。
归并 2→4→7 与 1→3→5：两个指针 p、q 各指两段头，比头取小，接到结果尾。
比两段头：左 2 vs 右 1。右 1 更小，取它。
把 1 接到结果尾（绿）。从右段取走的节点标灰，该段指针前移。
比两段头：左 2 vs 右 3。左 2 更小（相等优先取左·稳定），取它。
把 2 接到结果尾（绿）。从左段取走的节点标灰，该段指针前移。
比两段头：左 4 vs 右 3。右 3 更小，取它。
把 3 接到结果尾（绿）。从右段取走的节点标灰，该段指针前移。
比两段头：左 4 vs 右 5。左 4 更小（相等优先取左·稳定），取它。
把 4 接到结果尾（绿）。从左段取走的节点标灰，该段指针前移。
比两段头：左 7 vs 右 5。右 5 更小，取它。
把 5 接到结果尾（绿）。从右段取走的节点标灰，该段指针前移。
右段已空，把左段剩下的整段直接接上，当前接 7。
把 7 接到结果尾（绿）。从左段取走的节点标灰，该段指针前移。
2→4→7 与 1→3→5 合成有序段 1→2→3→4→5→7。
空 / 单节点 / 两节点是递归的出口与最小情形，先想清。
两个高频追问：迭代版降空间、快慢指针起点。
参考代码
def sortList(head): if not head or not head.next: return head slow, fast = head, head.next # 快慢指针找中点 while fast and fast.next: slow, fast = slow.next, fast.next.next mid = slow.next; slow.next = None # 从中点断开 left, right = sortList(head), sortList(mid) dummy = tail = ListNode() # 合并两条有序链 while left and right: if left.val <= right.val: tail.next, left = left, left.next else: tail.next, right = right, right.next tail = tail.next tail.next = left or right return dummy.next复杂度
- 时间：O(n log n)，log n 层递归，每层合并扫 n 个节点
- 空间：O(1)*，原地接线不新建节点；*递归栈 O(log n)
易错点
面试追问把动画讲成自己的话
追问如何把空间降到真正 O(1)（去掉递归栈）？
追问快慢指针为什么 fast 从 head.next 起？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
环形链表 II
LeetCode 142 · 中等 · 沿着 链表 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题