适用读者：链表题能看懂答案、自己一写就崩的人；以及准备面试、想把这题答出层次的人
技术栈：Python 为主，迭代与递归都附 Java 版
难度：简单（但它是 LC 23、LC 148 的地基，面试官都爱从这里起跳）
收获：哑结点的真实价值、一份不丢节点的迭代模板、递归写法的调用栈推演，以及「合并 K 个」的三种姿势
题目
将两个
升序链表合并为一个新的
升序链表并返回。新链表是通过
拼接给定的两个链表的所有节点组成的。
输入：l1 = [1,2,4]，l2 = [1,3,4]
输出：[1,1,2,3,4,4]
链表节点的定义（和上一篇 LC 206 一致，后面所有代码都用它）：
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
注意题目里「
拼接」两个字：不是让你 new 出一串新节点把值抄过去，而是
把原来的节点重新串起来。值一个都不改，改的只有
next 指针的指向。
这道题标着「简单」，通过率也确实高。但我见过不少人——包括一些刷了三百题的——在这题上写出过这两种代码：一种是接节点的时候把半条链接丢了；一种是写了五个
if 去处理「头节点到底是谁」，然后漏掉其中一种情况。
简单题的坑从来不在算法上，在
边界的完整性上。这篇就把这两个坑拆开看，然后给你一个坑都踩不到的写法。
一、先把「合并」翻译成指针操作
1.1 数组合并靠挪元素，链表合并靠改指向
数组怎么做归并？双指针比大小，把小的抄进新数组。
元素是要被复制搬运的，因为数组靠下标组织，你没法「把 a[2] 挂到 b 数组后面」。
链表不一样。链表的节点散落在堆里，唯一的组织方式是
next 指针。所以「把节点 X 放进结果链表」这件事，翻译成指针操作只有一句：
没有复制，没有搬移，就是
改一根指针。这也是为什么链表版归并的空间复杂度能做到 O(1)——结果链表用的全是现成的节点。
1.2 每一轮只做一件事：选一个人出场
两条链表都是升序的，所以
全局最小的元素，只可能出现在两条链表的头部。这就是合并的全部依据：
- 比较
l1 和 l2 的头节点，小的那个就是当前全局最小；
- 把它接到结果链表尾部，它对应的指针后移一格；
- 重复，直到某一条链表走空；
- 另一条剩下的部分直接整段接上——它本来就是有序的，而且每个值都不小于已接的所有值。
第 4 步是这道题最容易被忽略的一步，后面细说。
二、这道「简单」题的两个坑
坑一：接节点的时候，把后面半条链接丢了
链表节点的
next 只有一个格子。你把节点接到
tail.next 上之前，如果它后面还挂着东西，而你又需要用到那些东西——必须先把路记下来。
典型的错误是这样（伪代码）：
# 错误示范
tail.next = l1 # l1 接上结果链表
l1 = l1.next # 再往后走
这两行顺序
是对的。但初学者常写成下面的变体：先让
l1 = l1.next 再接，或者接完之后忘了前移
tail，下一轮又往
同一个 tail 后面接——上一个节点直接被覆盖，从结果链表里消失了。后者不会报错、不会异常，只有在输出的时候你才发现结果只有一两个节点。
判断标准很简单：改动任何一根 next 之前，先问自己「改完之后我还回得去吗」。
坑二：第一个节点接谁，是不确定的
假设不用任何技巧，直接开写。第一轮比较
1 和
1（两个头部），取
l1 的
1 当结果头。看起来没问题？把输入换成
l2 = [0, 3] 呢——头是
l2 的
0。
也就是说
结果的头节点可能来自任何一条链表的任何位置，没有哑结点的写法只能靠特判：
# 没有哑结点的写法：先花大力气确定头
if l1 is None:
return l2
if l2 is None:
return l1
if l1.val <= l2.val:
head = l1
l1 = l1.next
else:
head = l2
l2 = l2.next
tail = head
while l1 and l2:
... # 和正式循环一模一样的逻辑
return head
数一下：4 个特判分支 + 一个和正式循环几乎重复的初始化逻辑。重复意味着两处要同步维护，而同步维护的代码迟早改挂一处。
哑结点解决的就是这个。
三、哑结点：把「第一个节点」变成「普通节点」
哑结点（dummy node）是一个
不存任何有效数据的节点，值随便填，它的唯一工作是
预先占住结果链表的头：
dummy → ? → ? → ? → ∅ ← 结果链表，头被 dummy 占住了
tail ——^ ← tail 永远指向结果链表当前最后一个节点
有了它，之后每接一个节点，都是「接在
tail 后面」这个
普通操作——第一个接进来的节点，和第二十个接进来的节点，走的是
完全相同的代码路径。不再有任何「它是不是第一个」的判断。
最后返回的时候，真正的头是
dummy.next——dummy 自己只是个占位符，不进结果。
顺手理一下
tail 这个角色：它负责维护「
已拼接部分的边界」。所有拼接动作都发生在
tail 身后，
tail 之前的部分永远完整、永远有序、永远不再被碰。这个「维护一条已处理区边界」的思想，和 LC 206 里的
prev 指针是同一个东西——上一篇反转链表里的
prev，维护的是「已反转部分的头」。
下面这段动画把
1→2→4 和
1→3→4 合并的
完整 13 步演了一遍：绿色来自 A 链表，橙色来自 B 链表，虚线框是哑结点。注意看
tail 每一步怎么走、收尾那一歩「整段接上」长什么样。
看完动画，你应该对三个画面有印象：
compare 时两个候选节点同时高亮、
take 时节点飞进结果行并且颜色暴露了它的出身、
收尾时 B 剩下的那个 4 整段亮起来一次性接入。带着这三个画面，我们读代码。
四、迭代解法：逐行拆解
4.1 Python
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0) # 占位符，值无所谓
tail = dummy # tail 永远指向结果链表最后一个节点
while l1 and l2: # 两条都还有货，才需要比较
if l1.val <= l2.val: # 相等时取 l1，保证稳定性
tail.next = l1 # l1 的头接上结果
l1 = l1.next # l1 后移（先接，再走，顺序不能反）
else:
tail.next = l2
l2 = l2.next
tail = tail.next # tail 前移到新接的节点——忘了这行就是大事故
tail.next = l1 if l1 else l2 # 一方走空，另一方整段接上
return dummy.next # dummy 是占位符，真正的头在它后面
8 行有效代码。每一行都在干什么，对着动画再过一遍：
tail.next = l1 + l1 = l1.next：这就是坑一的安全顺序——先接、再走。接的时候 l1 还指着它，接完 l1 才挪走，没有任何信息丢失。tail = tail.next：坑一的第二半。接完新节点，边界要跟着走，否则下一轮又覆盖旧节点。tail.next = l1 if l1 else l2：坑四里的「最容易被忽略的一步」。循环退出的原因是某一方走空了，另一方剩下的节点一个都没接呢——整段接上。因为对方本来有序，而且头部的值不小于已拼接的所有值，直接接就是对的。
4.2 Java
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
4.3 拿示例走一遍
l1 = 1→2→4，
l2 = 1→3→4：
第 5 轮值得盯一眼：
l1 的
4 接上去之后
l1 走空，循环退出——但
l2 的
4 还悬在结果外面。没有收尾那行，输出就是
1→1→2→3→4，少了最后一个节点。这是这题提交记录里最常见的 Wrong Answer，没有之一。
4.4 边界全过一遍
- 一方为空（
l1 = []）：while 条件直接不成立，tail.next = l2 原样接上整条，返回。不需要任何特判——无哑结点写法里那 4 个分支，被哑结点无声地吞掉了。
- 双方都空：
tail.next = l2（也就是 None），返回 dummy.next 即 None。也对。
- 长度悬殊（
[1,5,9] 和 [2]）：循环 2 轮后 l2 走空，l1 剩 5→9 整段接上。和示例同一个形状。
- 相等值：
1 vs 1 取 l1。取 l2 结果也对（值相等），但 <= 有个说法叫稳定性——相等时先入者先出。合并链表本身看不出差别，可这个习惯会原样带进归并排序：稳定性是归并排序作为「稳定排序」的立身之本，而归并里干这活的正是这段合并代码。
五、递归解法：三行核心，栈要还债
5.1 代码
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
if not l1: # 一方空了，返回另一方
return l2
if not l2:
return l1
if l1.val <= l2.val: # 小的当头，它的 next 指向「剩下的合并结果」
l1.next = mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = mergeTwoLists(l1, l2.next)
return l2
Java：
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val <= l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
5.2 为什么这是对的
读懂递归只问一个问题：
mergeTwoLists(l1, l2) 的契约是什么？——「把这两条有序链表合并好，返回合并后的头」。
那么
l1.val <= l2.val 时，全局最小就是
l1 的头，它一定是新链表的第一个节点。剩下的部分呢？
l1.next 那半条和整条
l2 的合并——
和原问题一模一样，只是规模小了一格。把子问题的答案接到
l1.next 上，返回
l1，契约兑现。
递归的边界，恰好就是那两个「一方为空」的情况：空链表和任何链表合并，结果就是那条链表本身——
这题的递归边界就是数学上的单位元。
5.3 调用栈推演：1→2→4 × 1→3→4
压栈阶段（每层只做一件事：选出头，把剩下的交给下一层）：
merge(124, 134) 1≤1，头=1 → 等 merge(24, 134)
merge(24, 134) 2>1，头=1' → 等 merge(24, 34)
merge(24, 34) 2≤3，头=2 → 等 merge(4, 34)
merge(4, 34) 4>3，头=3 → 等 merge(4, 4)
merge(4, 4) 4≤4，头=4 → 等 merge(∅, 4)
merge(∅, 4) → 返回 4 ← 触底
回溯阶段（逐层把头接回去）：
merge(∅, 4) 返回 4
merge(4, 4) 4.next = 4 返回 4→4
merge(4, 34) 3.next = 4 返回 3→4→4
merge(24, 34) 2.next = 3 返回 2→3→4→4
merge(24, 134) 1'.next = 2 返回 1'→2→3→4→4
merge(124,134) 1.next = 1' 返回 1→1'→2→3→4→4
压到最深是 5 层，
恰好等于节点总数。这不是巧合：每层递归消耗一个节点，递归深度 = m + n。
5.4 递归的账单
Python 默认递归深度限制约 1000 层，两条各 600 节点的链表就能把它顶爆（
RecursionError）。所以工程上无脑选迭代；递归的价值在于
面试里证明你理解合并的自相似结构——以及它是下一节 LC 23 分治解法的零件。
六、复杂度
迭代：时间 O(m+n)——每个节点恰好被
tail 摸一次、被比较一次；空间 O(1)——只多了
dummy 和
tail 两个指针。
递归：时间同上；空间 O(m+n)——调用栈，上面推演过了。
注意 O(1) 这件事值得在面试里主动说：
链表版的归并不需要辅助数组，空间比数组版归并少一个 O(n)。这正是后面 LC 148（排序链表）要求 O(1) 空间解法时，必须用链表归并的原因。
七、追问：合并 K 个呢？（LC 23）
这道题在面试里几乎从不单独出现，它的标准续命方式是：「
那如果是 K 条链表呢？」（LeetCode 23，困难）。
7.1 笨办法：复用本题，两两顺序合并
拿着本题的解法，从
lists[0] 开始逐条往后合：
result = lists[0]
for lst in lists[1:]:
result = mergeTwoLists(result, lst)
对，但慢。第 i 轮合并时，
result 已经长到约
i·N 个节点（K 条各长 N），每轮都是 O(iN)，总时间
O(k²N)。瓶颈在于：早期接进 result 的节点，会被后面每一轮
反复摸一遍。
7.2 分治：两两配对，轮数从 k 变成 log k
第一轮 K 条两两配对合并成 K/2 条，第二轮 K/4 条……像锦标赛一样，总共 ⌈log k⌉ 轮，每轮总工作量都是 O(N)（所有节点恰好被摸一次），总时间
O(N log k)。LeetCode 官方题解管这个叫「分治合并」，结构上就是归并排序的归并树倒过来。
7.3 最小堆：只把 K 个头放进堆
更常见的面试写法。关键观察：
任何时刻，全局最小只可能是 K 条链表各自的头——和本题「最小只能在两个头部产生」是同一件事的 K 元版。所以堆里
永远只放 K 个节点，不用装下全部 N 个：
import heapq
def mergeKLists(lists):
dummy = ListNode(0)
tail = dummy
heap = []
for i, head in enumerate(lists): # K 个头入堆
if head:
# ListNode 没法比较大小，塞个序号 i 垫背：
# 值相同时按 i 比，永远不会比较到 node 本身
heapq.heappush(heap, (head.val, i, head))
while heap:
val, i, node = heapq.heappop(heap)
tail.next = node
tail = tail.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
时间 O(N log k)——每个节点进出堆各一次，堆里始终只有 K 个元素；空间 O(k)。
注意结构上的传承：dummy、tail、先接再走、比较取小——堆版和本题迭代版
骨架完全一样，只是「选最小的头」从一个
if 变成了堆。你把 LC 21 吃透，LC 23 的三种写法里有两种是白送的。
7.4 顺手埋个钩子
本题真正的「大号应用场景」是
LC 148 排序链表：链表归并排序 = 快慢指针找中点 + 递归排两半 +
本题的合并作为 merge 步骤。要求 O(1) 额外空间时，只有链表归并能做到（自底向上迭代版），而它的核心就是本文第四节的 8 行代码。所以面试官问这题，深层动机经常是探一探你后面能不能接住 148。
八、常见坑清单
提交前 / 写完代码后按这个清单过一遍：
- 收尾忘了整段接上：
tail.next = l1 if l1 else l2 漏掉，长输入直接少一截。本题 WA 排行榜第一名。
tail 忘了前移：所有节点都往同一个 tail 后面接，前面的被覆盖，输出只剩一两个节点，还可能成环。while 条件写成 or：while l1 or l2 进循环后取 l1.val，l1 是 None 就当场 AttributeError。循环条件必须是 and，把「一方走空」交给收尾处理。- 先走后接：
l1 = l1.next 写在 tail.next = l1 前面，节点还没接上指针就挪走了，直接丢节点。
- 相等值用
<：结果不错，但稳定性没了，而且面试官会问一句「为什么这里用 <=」——答案在 4.4 节。
- 递归版用在超长链表上：栈深 O(m+n)，Python 里约 1000 层就到顶。面试可以写递归，但要主动说清这个代价，然后说「工程实现用迭代」。
- new 新节点抄值：题目要求拼接原节点；抄值的写法多花 O(m+n) 空间，还可能被面试官认为没读懂题。
九、面试怎么答
30 秒版本：
哑结点 + tail 指针的迭代。循环里比较两个头，小的接到 tail 后面、指针后移、tail 前移；循环退出说明一方走空，另一方剩余部分整段接上——因为有序且都不小于已拼接部分。时间 O(m+n)，空间 O(1)，dummy.next 就是答案。
追问预判：
- 「为什么需要哑结点？」→ 第一个节点的来源不确定，没有它就得为「头是谁」写一串特判；有了它，第一个节点和后面的节点走同一条代码路径。
- 「还有别的写法吗？」→ 递归，三行核心；但栈深 O(m+n)，长链表会爆，工程上选迭代。
- 「相等值取哪边？」→ 任意一边都对，习惯取 l1 保稳定，这个习惯在归并排序里是必需品。
- 「K 条链表怎么合？」→ 顺序两两 O(k²N) → 分治两两 O(N log k) → 最小堆 O(N log k)/空间 O(k)，堆里只放 K 个头。
- 「链表归并和数组归并的区别？」→ 链表拼接不改值、不改数组，合并这步 O(1) 额外空间——这是 LC 148 能做 O(1) 空间排序的原因。
结语
把这篇和上一篇 LC 206 放在一起看，会发现两个「简单」题其实在教同一件事：
指针操作的本质是维护边界。206 里的
prev 守着「已反转区」，21 里的
tail 守着「已拼接区」——所有危险动作都发生在边界身后，边界之前的东西永远完整、永远不用再回头检查。
所谓「写链表题不慌」，不是背下多少模板，而是每动一根指针之前都清楚：它属于已处理区，还是待处理区，这一改会不会把回头的路堵死。
下一篇大概率是 LC 148——把这两题拼起来，你就有了一个 O(1) 空间的链表归并排序。刷题这条线，到那里才算真正串成串。