两条链都已排好序，合并时为什么还要先挂一个空节点
合并两个有序链表是归并排序中 merge 步骤的链式版本：每次比较两条链的队首，把较小的那个节点整节点摘下来接到结果尾部，一条耗尽后把另一条剩余整段接上。它常被当成一道简单题，真正的失分点却在收尾与所有权：忘了接剩余段会丢节点，新建节点复制值会把 O(1) 空间变成 O(n)，用小于而不是小于等于会破坏稳定性，递归写法还会压出 O(m+n) 的调用栈。本文从哨兵节点与循环不变量讲起，说明原地拼接为什么可行、数组归并为什么反而需要辅助空间，并给出面试追问与工程落地的判断标准。
是什么
合并两个有序链表，指的是给定两条按值非降序排列的单链表，把它们的所有节点合并成一条仍然有序的链表。它本质上就是归并排序里 merge 这一步在链式存储上的实现：数组归并通常要另开一块缓冲区按序写入，链表归并只需要改 next 指针，把已有节点重新串起来。
一句话直觉：像两个窗口各排了一队号数递增的顾客，收银员每次只比较两队队首，号小的先办；某一队空了，就把另一队剩下的人整队带过来，不必再一个个叫号。
典型场景包括链表归并排序、多路归并的外部排序、把多条按时间戳排好的日志流合成一条、数据库的 sort-merge join，以及面试里最常见的 LeetCode 21。它之所以反复出现，是因为题目足够短，却同时考了指针操作、边界处理、空间复杂度与稳定性四件事。
核心原理
迭代解法只需要三个指针，但必须先把不变量说清楚：
l1、l2分别指向两条链表中尚未处理部分的第一个节点；tail指向已合并部分的最后一个节点；dummy是一个不存有效值的哨兵，dummy.next最终就是结果的头。
每一轮比较 l1.val 与 l2.val，把较小的那个节点整节点接到 tail.next，然后让该链表的指针后移，tail 随之前移。循环在任一条为空时结束，此时把另一条的剩余整段直接挂到 tail.next。剩下的部分之所以能整段接，是因为它本来就有序，且每个值都不小于已合并部分的最后一个值。
def merge(l1, l2):
dummy = tail = ListNode(0)
while l1 and l2:
if l1.val <= l2.val: # 取等号，保证稳定
tail.next, l1 = l1, l1.next
else:
tail.next, l2 = l2, l2.next
tail = tail.next
tail.next = l1 or l2 # 剩余整段一次接上
return dummy.next哨兵的价值在于消灭“结果链表还是空的”这个特殊状态。没有它，第一轮必须单独判断该把谁设为头，代码里就多出一段只在第一次执行的分支；有了它，头节点和中间节点走同一条赋值路径，空输入也自然退化成返回 None。这是典型的用一点冗余换掉一类边界 bug。
第二个容易被忽略的点是所有权。上面接上去的是节点本身，不是复制出来的新节点，所以合并完成后，原来两条链表的结构已经被拆散，调用方手里的旧头指针不再代表一条完整的链。这种“破坏性”正是 O(1) 额外空间的来源：除哨兵外没有分配任何节点。如果业务上还要保留输入，就必须显式复制，空间随之变成 O(n+m)，这两件事不能同时要。
第三个点是稳定性。所谓稳定，指值相等的节点在合并后仍保持原来的相对次序。把比较写成 l1.val <= l2.val，相等时优先取第一条链的节点，稳定性就成立；写成严格小于，相等节点会被后一条链的节点插到前面，链表归并排序的结果就不再稳定。这一点在只要求“合并后有序”的题目里看不出来，但一旦这步被嵌进排序算法，影响的是整体正确性。
最后是递归写法。它的形式很漂亮：较小者作为头，其 next 等于“剩下部分与另一条链的合并结果”。但递归深度等于合并后的总长度，最坏是 O(m+n)。Python 默认递归深度约一千，两条十万节点的链会在递归版上直接栈溢出；而且这不是尾递归，多数语言不会把它优化成循环。所以“递归版空间 O(1)”是错误说法，它的额外空间是调用栈。
常见考点与误区
- 误区一：循环结束就返回，忘了接剩余段。 面试官往往专挑“一条链比另一条短很多”的用例，此时结果会静默丢掉一整段节点。正确做法是循环后一句
tail.next = l1 or l2，不要再写一个 while 逐个搬运。 - 误区二：认为必须新建节点。 新建节点复制值确实不破坏输入，但空间是 O(n+m)；题目若要求原地合并，考的就是改指针。反过来，面试时先问一句“是否允许修改输入”，比背模板更能加分。
- 考点三：为什么用哨兵，返回的却是
dummy.next。 答“方便”不够，要说出它把“设置头节点”和“追加节点”合并成同一路径。C++ 里还要注意dummy是栈上对象，返回它的地址会得到悬垂指针。 - 考点四：稳定性的条件。 常见问法是“相等时取哪条链的节点”。答“随便取”就错了；取第一条链、比较用小于等于，才能保持相对次序。这也是归并排序能稳定的关键。
- 考点五：复杂度到底是多少。 时间是 O(m+n)，每个节点只被访问常数次；空间要区分迭代与递归：迭代是 O(1)（不计输入与哨兵），递归是 O(m+n) 的栈。把递归说成 O(1) 是高频扣分点。
- 考点六：k 条有序链表怎么合。 两两合并最坏要扫很多遍，复杂度 O(kN)；用大小为 k 的最小堆每次取全局最小，是 O(N log k)。Python 的堆里如果放节点本身会因不可比较而报错，通常存
(val, 链表下标, 节点)三元组。
实践建议
- 先问约束再动手：是否允许破坏输入、是否要求稳定、有序是升序还是降序、链表规模多大。这四个答案分别决定要不要复制、比较符怎么写、要不要反转、用迭代还是递归。
- 生产代码首选迭代加哨兵。递归只适合长度有界或纯教学的场景；线上处理未知长度的链，栈溢出是概率问题，不是理论问题。
- 单测覆盖五类边界：两条都为空、其中一条为空、两条各一个节点、一条完全小于另一条、存在大量相等值。最后一类专门验稳定性，只测“结果有序”是测不出来的。
- 在归并排序里用自底向上的迭代归并，按步长 1、2、4 逐层合并，可以避开 O(log n) 的递归栈；合并内层用小于等于，整体稳定性才有保证。
- 不要把链表的写法照搬到数组。数组归并通常需要 O(n) 辅助数组；若目标数组尾部有空位，从后往前填能省掉这块空间。外存排序则用多路归并加堆，并尽量让读写保持顺序，减少随机寻道。
- 注意常数：链表合并虽然空间省，但每次比较都要跳指针，缓存命中率不如数组顺序扫描。数据量小且只合一次时，不必为了 O(1) 空间放弃更简单可读的实现。
一句话总结：合并有序链表考的不是比较大小，而是指针归属与收尾——哨兵消灭头节点特判，整段接上省掉最后一轮搬运。