LeetCode Hot100 里的那道 148. 排序链表是我做模拟面试时见过翻车率最高的题目之一。这道题选进高频题列表不是因为链表的排序有多难而是它一次性把链表遍历、双指针、分治、合并四个基本功全考了一遍。很多人背过快速排序、背过数组归并但一碰上链表就不知道该从哪下手更多人第一反应是把链表转成数组排完再串回去提交能过面试却可能被一句话打回来“你这样做的空间复杂度是多少”如果你正在刷 Hot100或者准备算法面这道题值得你花一整个晚上吃透。今天这篇我会把它的底层原理、两种归并写法、还有面试里的追问细节全部摊开讲。1. 题目到底考什么从一道排序题看链表特性1.1 题目在说什么原题描述其实很短给一个单链表的头节点 head按升序把它排好返回排序后的链表头。链表节点定义非常简单一个 val一个 next。看起来不就是排序吗但有三个硬性限制时间复杂度 O(n log n)空间复杂度 O(1)并且只能操作链表本身。这三个词放在一起基本排除了大多数“偷懒”方案。如果你第一时间想到“把链表所有节点的值放进数组排序再重新串起来”我得说这个方向不是不能用但它在面试中风险很高。原因很直接拷贝节点值需要 O(n) 空间排序后的数组还要再遍历一遍更新节点整体空间不是常数级更重要的是你没有展示任何链表的操作能力而面试官要考察的恰恰是你能不能在不依赖额外存储的情况下靠指针把链表重新组织好。所以这道题从设计上就是在逼着你用链表思维去解决排序问题。1.2 链表的三个“不友好”特性为什么同样排序数组可以放心用归并、快排、堆排放到链表上就变味因为链表有三个和数组完全不同的特性。不能随机访问数组可以用下标 O(1) 取任意元素链表只能从 head 一个一个 next 走到目标位置找中点都得靠快慢指针走一趟。单向性绝大多数链表题都是单链表只有 next 没有 prev意味着你无法从后往前遍历很多倒序操作必须借助递归栈或者反转链表。指针操作容易断链数组交换元素只需借助临时变量链表则要处理多个节点之间的引用关系一个疏忽就是把整条链弄丢或者弄出环。这三个特性决定了一个排序算法如果依赖随机访问比如堆排序在链表上实现起来非常别扭如果依赖从后往前扫描比如标准快排的 partition单链表也得改造成双向链表或者用递归模拟。所以选算法的时候必须找一个和链表物理结构最匹配的策略。1.3 顺带复习哑节点的使用场景链表题目里dummy node哑节点是我最常用的技巧。它本质上是创建一个假的头节点让它的 next 指向真正的头节点这样你在头节点位置做插入、删除时就不需要单独判断 head 是否为空、是否要更新 head。排序链表这道题里自顶向下的合并函数用到了 dummy自底向上的整体过程更依赖 dummy因为每轮排序结果的头节点都可能变化用 dummy 统一处理最后返回 dummy.next 即可。很多初学者觉得 dummy 是多余的直到写自底向上版本时才发现没有它处理第一次合并和后续合并的边界条件会繁琐到爆炸。我建议你把 dummy 当作一个标准姿势练到条件反射。2. 为什么归并排序是链表排序的最优解2.1 快速排序在链表上为什么别扭很多人会问快速排序平均也是 O(n log n)为什么不用它不是不能用而是不舒服。快排的核心是 partition选定一个 pivot把小于它的放左边大于它的放右边。数组中我们可以从两端向中间扫描链表不行只能从头走到尾把小于 pivot 的节点拆出来再把大于等于的拆出来最后递归处理两条链。整个 partition 过程要维护很多指针而且如果 pivot 选不好链表快排非常容易退化到 O(n^2)。我之前用链表实现过一次快排代码长度大约是归并排序的1.5倍边界条件还多面试时写出 bug 的概率很高。不是说你不能答而是性价比不高。2.2 归并排序为什么契合链表归并排序的核心操作是两个把序列对半分成两段再把两个有序序列合并成一个有序序列。把第一个操作翻译成链表就是“找中点 断开”把第二个操作翻译成链表就是“双指针遍历两条链逐个挑小的节点接上”。这两个操作在链表上都只需要 O(1) 额外空间和 O(n) 时间没有任何随机访问需求。所以归并排序几乎就是为链表量身定做的排序方案。从稳定性角度看归并排序也是稳定排序。合并两个有序链表时只要在值相等时优先取左边链表的节点就能保证原链表中的相对顺序不被破坏。这在某些场景下很关键比如需要按多个字段排序第一阶段已经排好序第二阶段再排序时要求相对顺序稳定归并能满足这一点快速排序通常做不到稳定。2.3 复杂度到底怎么算我们先说时间。每次把链表切成两段需要走一遍找中点时间复杂度 O(n)。递归深度是 log n 层每层需要合并的总节点数是 n所以总时间是 O(n log n)。这个复杂度无论数据初始状态如何都是稳定的因为链表归并总是严格对半切不像快排那样依赖 pivot 质量。再说空间。这里有个很多人会忽略的细节如果使用递归的自顶向下归并递归调用栈的深度是 O(log n)所以总空间是 O(log n)不是 O(1)。LeetCode 的原题描述写的是“O(1) memory”有些语言会有尾递归优化但链表切分递归是两路递归通常不会被优化。所以严格来说要满足题目的 O(1) 空间要求必须用下面要讲的自底向上迭代版本。但是很多面试官也接受递归版本前提是你能说清楚空间复杂度区别再主动优化成迭代版。2.4 一个最小示例看明白归并过程如果觉得抽象拿一个具体链表走一遍就清楚了。假设链表是 4 - 2 - 1 - 3。自顶向下归并先把链表从中间拆成 4 - 2 和 1 - 3继续拆成 4、2、1、3 四个单节点。然后从最底层开始合并4 和 2 合并成 2 - 41 和 3 合并成 1 - 3最后合并这两个有序链表依次比较两个头节点得到 1 - 2 - 3 - 4。整个过程可以看作“先拆到底再两两合并”每一层合并都是完全相同的逻辑。自底向上除了不递归先按长度为1的子链表合并成2再按长度为2的子链表合并成4最终效果和自顶向下完全一致只是顺序反过来。理解这个最小例子后面的代码就不会觉得乱了。3. 自顶向下归并最直观的递归写法3.1 递归三件事自顶向下归并的思路和数组归并一模一样区别只是把“对半切”换成了“链表找中点并断开”。base case链表为空或只有一个节点天然有序直接返回。分割用快慢指针把链表切成左右两半。合并递归排序左右两半然后把两个有序链表合并成一个。这个递归顺序需要特别注意一定是先通过快慢指针找到右半部分起点 mid再把 slow.next 置空让左半独立。很多新手先递归调用再去找中点结果原链表已经被修改了自然就出错了。3.2 快慢指针找中点为什么 fast 要从 head.next 起步找链表中点的标准办法是快慢指针slow 每次走一步fast 每次走两步fast 到终点时 slow 正好在中点。但这里有一个小坑如果初始化 slow head, fast head那么对于只有两个节点的链表slow 最终会走到第二个节点mid slow.next 是 None左半部分反而变成整个链表右半为空递归永远无法结束。所以正确写法是 slow head, fast head.next。这样两个节点时 fast.next 为 None循环不进入slow 停在 head右半从 head.next 开始左半只有第一个节点拆分正确。代码如下def getMid(head): slow, fast head, head.next while fast and fast.next: slow slow.next fast fast.next.next mid slow.next slow.next None return head, mid这里有一个关键动作slow.next None。如果不把左右两半断开后面递归排序时两个子链表会交错在一起合并结果会非常诡异。断开后head 到 slow 是左半mid 到末尾是右半两边互不干扰。3.3 合并两个有序链表的通用写法合并两个有序链表也是一道独立的基础题用 dummy node 可以省去大量空指针判断。核心逻辑是新建一个哑节点用一个 cur 指针始终指向合并链表的尾部然后比较 l1 和 l2 当前节点的值把小的那个接上去并让对应链表指针后移。循环结束后如果某条链还有剩余直接把剩余部分接到 cur.next。def merge(l1, l2): dummy ListNode(0) cur dummy while l1 and l2: if l1.val l2.val: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next cur cur.next cur.next l1 if l1 else l2 return dummy.next这里用 而不是 是为了保证相同值的情况下优先取左链的节点让排序保持稳定。如果你的面试官对稳定性有要求这一行就能体现你的基本功。3.4 合并到 sortList 主体有了切分和合并主体就非常短了def sortList(head): if not head or not head.next: return head head, right getMid(head) left sortList(head) right sortList(right) return merge(left, right)这里先把 getMid 返回的左右半重新赋值再分别递归排序。别忘了递归排序后head 指向的链表已经被修改left 才是排序后左半的头。建议全程用变量接收返回值不要再用原来的 head 引用避免混淆。为了验证可以在本地跑两个用例输入 [4,2,1,3] 应该输出 [1,2,3,4]输入 [-1,5,3,4,0] 应该输出 [-1,0,3,4,5]。我习惯再跑两个边界空链表 None 和单节点 [1]这两个必须原样返回。4. 自底向上归并O(1)空间的硬核写法4.1 递归栈空间的问题前面已经提到自顶向下递归虽然思路清晰但每一层递归都会在调用栈上留下一个帧深度 log n总空间 O(log n)。题目要求 O(1) memory严格做的话必须改成迭代。其实自底向上的思路也不复杂先把链表看成一个个长度为 1 的有序子链表然后相邻的两个子链表合并成长度为 2 的有序子链表再合并成长度为 4816……直到整个链表有序。整个过程不需要递归只需要循环用的是有限几个指针空间自然就是 O(1)。4.2 自底向上的三轮循环具体实现分成两层循环。外层循环控制子链表长度 subLen从 1 开始每次乘以 2直到 subLen 大于等于链表总长度。内层循环每轮从当前链表的头部开始按 subLen 切出 left 和 right 两个子链表合并之后接到已经排好的结果链后面。内层循环里有几个量需要维护dummy 是最终结果链表的哑节点prev 始终指向结果链表的末尾方便把下一段合并结果接上去cur 是当前扫描原链表的指针。每次先检查 cur 是否为空为空表示这一轮所有子链表都处理完了。处理完一整轮后把 cur 重置为 dummy.next也就是新排序链表的头继续下一轮更大的 subLen。切分子链表的时候要注意长度可能不足 subLenleft 的长度取 cur 到第 subLen 个节点如果不足就取到链表末尾right 从 left 后面继续取 subLen 个同样可能不足。切好后left 和 right 通过 merge 合并并让 prev.next 指向合并后的头prev 再移动到合并后链表的末尾。还要把 cur 移动到 right 段原来的末尾的下一个节点继续处理下一组相邻子链表。4.3 完整代码与逐行说明来看完整代码def sortList(head): if not head or not head.next: return head # 统计链表长度 length 0 node head while node: length 1 node node.next dummy ListNode(0) dummy.next head subLen 1 while subLen length: prev dummy cur dummy.next while cur: # 切出 left 子链表 left cur cnt 1 while cnt subLen and cur.next: cur cur.next cnt 1 # 此时 cur 是 left 段的最后一个节点 right cur.next cur.next None # 断开 left # 切出 right 子链表 cnt 1 cur right while cnt subLen and cur and cur.next: cur cur.next cnt 1 # 记录下一段起点并断开 right next_start None if cur: next_start cur.next cur.next None # 合并 left 和 right merged merge(left, right) prev.next merged # prev 移动到合并后的末尾 while prev.next: prev prev.next # 继续处理下一组 cur next_start subLen 1 return dummy.next这段代码有几个容易错的地方我逐个说。首先是 right 可能为 None就是 cur.next 已经是空的情况表示没有第二段子链表直接把 left 当作合并结果接上去。这时候也可以直接把 left 接到 prev.next不调用 merge因为一个有序链表不需要合并。但为了代码统一merge 内部已经处理了 None所以直接调用没问题。其次是切完 left 后 cur.next None 的位置必须在保存 right 之后执行否则 right 指针会丢掉。我见过很多次这个错误。同样切完 right 后要把 next_start 先保存再把 cur.next 置空顺序反了就找不到下一轮的入口。最后是 prev 的移动。合并后的链表可能长达 2 * subLen我们要把它移动到末尾这样下一段合并结果才能正确接在后面。有一个小优化直接先保存合并前 left 和 right 各自长度合并后末尾就是原 right 段的末尾。不过用 while 循环移动也没有性能问题因为每轮每个节点最多被 prev 走一遍总体还是 O(n)。4.4 为什么空间是 O(1)整个迭代过程只用了 dummy、prev、cur、left、right、next_start 这几个指针没有任何递归调用也没有使用和 n 相关的额外存储。merge 函数内部同样只用了 dummy 和 cur。所以额外空间是固定常数符合题目的 O(1) memory 要求。时间复杂度依然是 O(n log n)每轮外层循环需要遍历完整个链表轮数是 log n每轮 O(n)。提示如果你在面试里先写递归版本面试官追问“内存复杂度是多少”你紧接着写出这个迭代版并且说明“递归版栈深度是 log n因为用了系统栈迭代版只用常数指针”这一来一回的对比很容易让面试官给高分。5. 常见问题与面试追问实录5.1 刷题高频错误速查表这一节整理我刷题和陪跑时遇到的典型问题按“错误现象 / 根本原因 / 解决方法”列出来。错误现象根本原因解决方法递归排序后链表出现环拆分左右时没有断开 slow.next 或 cur.next每次切分后把中间节点 next 置 None找中点死循环fast 初始化成 headfast 应初始化为 head.next合并后丢节点合并前没保存 right 或 next_start切断 next 之前先保存右侧起点自底向上结果少一段内层循环里 cur 没正确跳到下一段切完 right 后把 cur 置为 next_start递归版报栈溢出递归深度超过系统限制链表特别长改用自底向上迭代版这些都是真实会反复踩的坑尤其最后一个。LeetCode 有些测试用例链表很长递归深度 log n 一般没问题但如果是极端失衡的递归写法就会出问题。在本地编译器上跑长链表时也需要注意。5.2 面试官爱问的几个“为什么”为什么不能用堆排序堆排序在数组上很棒但链表无法 O(1) 访问任意下标建堆和调整堆都要跳到指定位置每次都要遍历链表时间复杂度直接退化到 O(n^2)。插入排序不是能原地吗链表插入排序确实可以原地但最坏时间复杂度 O(n^2)不满足题目要求。LeetCode 147 专门考链表插入排序你可以对比着练。归并排序稳定吗稳定。只要在合并时值相等优先取左边链表的节点就能保持原顺序。自底向上同样可以做到稳定。如果链表是双向链表呢双向链表的排序复杂度下界还是 O(n log n)但某些操作更方便比如快排可以从两端扫描 partition。不过单链表用归并已经是最优复杂度了。如果链表长度未知自底向上需要先遍历一遍求长度能避免吗可以每轮从头部开始扫描边数边切但实现会更复杂而且多一次全遍历其实不算额外空间。多数面试场景下先求长度是最清晰的方案。5.3 从这道题延伸出去的工程价值很多人觉得链表排序是纯面试题实际工程中碰不到。这话只说对一半。像是外部排序里内存不能一次性装下所有数据时会把数据分块排序再合并归并排序就是核心思想。而链表的归并能力在很多底层库和中间件里也有体现C 标准库里 list::sort 用的就是归并排序的迭代实现Java 的 Collections.sort 对链表也有归并排序路径。刷这道题其实是在刷“分治合并”这个通用套路后面你遇到合并 K 个有序链表、区间合并、外部排序都会用到同一套思维。另外这道题还能帮你练熟哑节点、快慢指针、链表断链与拼接。这三个技巧几乎覆盖了链表题的一半考点。我自己刷链表题时只要遇到需要在头部插入、需要找中间位置、需要拆分链表都会联想到这道题里的动作。所以说它是 Hot100 里最值得反复练的“母题”之一并不夸张。5.4 刷题顺序建议与最终心得如果你现在刚接触这道题我的建议是不要直接背代码。第一步先写一个合并两个有序链表的函数并保证能处理空链表。第二步写一个快慢指针找中点并断开的函数多测试长度为2、3、4的链表。第三步把两者拼成递归版。第四步在你对递归版足够熟之后再挑战自底向上迭代版。这个过程看起来慢但一旦建立起“归并切分合并”的思维链表类的分治题你基本都能拿下。我在带刷题的朋友时经常强调一个点算法题不是比谁背得多而是比谁能从一道题里总结出一类题的方法。148 题就是典型的“一道题带一类题”。你今天把它的递归版和迭代版都吃透后面面试遇到任何链表排序问题都不会慌。