企业官网建设流程全解析

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 -> 4，1 和 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 的有序子链表，再合并成长度为 4，8，16……直到整个链表有序。整个过程不需要递归，只需要循环，用的是有限几个指针，空间自然就是 O(1)。

4.2 自底向上的三轮循环

具体实现分成两层循环。外层循环控制子链表长度 subLen，从 1 开始，每次乘以 2，直到 subLen 大于等于链表总长度。内层循环每轮从当前链表的头部开始，按 subLen 切出 left 和 right 两个子链表，合并之后接到已经排好的结果链后面。

内层循环里有几个量需要维护：dummy 是最终结果链表的哑节点，prev 始终指向结果链表的末尾，方便把下一段合并结果接上去；cur 是当前扫描原链表的指针。每次先检查 cur 是否为空，为空表示这一轮所有子链表都处理完了。处理完一整轮后，把 cur 重置为 dummy.next，也就是新排序链表的头，继续下一轮更大的 subLen。

切分子链表的时候要注意长度可能不足 subLen：left 的长度取 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 刷题高频错误速查表

这一节整理我刷题和陪跑时遇到的典型问题，按“错误现象 / 根本原因 / 解决方法”列出来。

这些都是真实会反复踩的坑，尤其最后一个。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 题就是典型的“一道题带一类题”。你今天把它的递归版和迭代版都吃透，后面面试遇到任何链表排序问题，都不会慌。