题目描述
思路解析动画文字版
数组排序爱用快排，靠下标左右跳。可链表只能一根一根顺着走，没有下标，快排的随机访问就废了。
归并排序天生适合链表：它只要能顺着 next 往后走、再把节点一个个接起来。这两件事链表都很擅长，所以选它。
整体思路：切半 → 递归 → 合并：归并三步：先把链表从中间切成两半，递归地各自排好序，最后把两条有序链表合并成一条。下面慢放这三步。
1. 快慢指针找中点 · 起步：slow 从第 1 个出发，fast 从第 2 个出发。fast 每次跳 2 步、slow 每次跳 1 步，fast 到尾巴时 slow 正好停在前半段的末尾。
1. 快慢指针找中点 · 走一轮：走一轮：slow 跳到值 2，fast 跳到值 3。再看 fast.next 已经是空，循环停下。此刻 slow 停在前半段的最后一个节点 2 上。
2. 从中点断开成两段：mid 记下 slow 后面那个节点（值 1），再把 slow.next 剪成空。一刀下去，链表断成左半 4→2 和右半 1→3 两条独立的链。
3. 递归排左半 4→2：对左半 4→2 再递归：切成单个 4 和单个 2，单节点天然有序，合并时 2＜4，所以接成 2→4。左半排好了。
4. 递归排右半 1→3：右半 1→3 同样切半再合并，1＜3 本就有序，得到 1→3。现在两条短链都各自有序，准备合并。
5. 合并 · 比较两个头：合并开始：比左半头 2 和右半头 1。1 更小，把 1 接到结果链尾，右半的 b 指针往后挪到 3。
6. 合并 · 接第二个：再比：左半头 2 和右半头 3，2 更小。把 2 接上结果，左半的 a 指针挪到 4。结果链现在是 1→2。
7. 合并 · 接第三个：继续比：左半头 4 和右半头 3，3 更小。接上 3，右半走到头变空。结果链是 1→2→3，只剩左半的 4 还没接。
8. 合并 · 接上剩余尾巴：右半空了，左半还剩一个 4。归并的收尾招：哪边没走完，就把它整条直接接到结果尾巴。最终得到 1→2→3→4，排序完成。
一句话本质：把长链对半切到不能再切，再一层层合并回来。链表只用得着「往后走」和「接节点」，所以归并最顺手。
雷区实演：fast 起点错了会怎样：拿两节点 4→2 试：若 slow、fast 都从头起步，fast 跳到 2、fast.next 为空就停，slow 还停在 4。mid 仍是整条、左半也是整条，根本没切开，递归会原地打转。所以 fast 必须从 head.next 起步。
面试追问：三个高频追问：为何弃快排、如何做到 O(1) 空间、稳定性，都从动画里的切半与合并讲起。
迁移阶梯：这题是两个基本功的组合：第 876 题「链表中间结点」练快慢指针切半，第 21 题「合并两个有序链表」练合并，吃透它们，本题就是把两者拼起来。卡住可以问问 AI 助教小欧，或去链表专题通关训练。
边界三连：排序链表的边界先看空链、单节点和两节点：前两个靠首行 if 拦住，两节点专门验证快慢指针起点对不对。
参考代码
class Solution: def sortList(self, head): if not head or not head.next: return head slow, fast = head, head.next while fast and fast.next: slow = slow.next fast = fast.next.next mid = slow.next slow.next = None left = self.sortList(head) right = self.sortList(mid) return self.merge(left, right) def merge(self, a, b): dummy = tail = ListNode(0) while a and b: if a.val < b.val: tail.next, a = a, a.next else: tail.next, b = b, b.next tail = tail.next tail.next = a or b return dummy.next复杂度
- 时间复杂度：O(n log n)，每层合并要走遍全部 n 个节点，链表对半切共 log n 层，n×log n
- 空间复杂度：O(log n)，不开新数组，唯一开销是递归调用栈，深度等于切分层数 log n
可套用的代码模板
把骨架记成三步：边界返回 → 快慢切半并断开 → 递归两半后合并。merge 部分留给你照参考代码默写，三语言结构一致。
def sortList(head): # 边界：空或单节点直接返回 if not head or not head.next: return head # ① 快慢指针找中点（fast 从 head.next 起） slow, fast = head, head.next while fast and fast.next: slow, fast = slow.next, fast.next.next # ② 断开：记下右半头，剪断左半尾 mid = slow.next slow.next = None # ③ 递归排两半，再合并 return merge(sortList(head), sortList(mid))易错点
面试追问把动画讲成自己的话
追问为什么不直接快排链表？
追问题目说尽量 O(1) 空间，递归版是 O(log n)，怎么做到真 O(1)？
追问归并排序为什么是稳定的？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
环形链表 II
LeetCode 142 · 中等 · 沿着 链表 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题