先说个有意思的现象。合并两个有序链表在LeetCode上难度标着 easy可我在面试别人的时候见过太多人在它身上栽跟头有人写出来的代码三四十行还全是 if 分支有人在 while 循环里忘了把 cur 指针往后挪结果死循环还有人连空链表都没判断就直接访问l1.val抛异常。这道题本身不难难的是你能不能把它写得干净、讲得清楚、扩展得动。这篇博文会从两条主线展开迭代解法里的哨兵节点设计以及递归解法里的子问题拆解。顺便把边界条件、复杂度、本地测试用例这些容易被忽略但又特别影响面试观感的东西一次性聊透。适合正在刷 LeetCode 热门 100 题的读者也适合想系统梳理链表题型的老手。1. 为什么合并两个有序链表值得反复研究1.1 面试频率与隐藏考察点合并两个有序链表之所以能进 LeetCode 热门 100 题不是因为算法有多难而是因为它恰好是面试官最爱用来摸底的题目之一。链表相关的题目有很多反转链表、删除倒数第 N 个节点、寻找中点各有各的侧重点但合并两个有序链表考察的是一种复合能力你需要在同一时刻管理至少三个指针并且在每一步都清楚它们分别指向哪里。很多刷题的朋友有个误区觉得 easy 题没什么含金量把大量时间花在 hard 题上。但实际面试中easy 题的出现频率远高于 hard 题。面试官真正想看的是你写 easy 题时的代码习惯命名是否清晰、边界条件是否覆盖、退出循环后剩余节点有没有接上。这些细节恰恰是合并两个有序链表能全部暴露出来的。1.2 两种解法对应两种思维模型这道题特别的地方在于它同时支持迭代和递归两种主流解法而且两种解法的思维模型完全不同。迭代解法要求你维护循环不变量——每一步执行完后当前已合并的链表都保持升序递归解法要求你写出递推关系——把合并两个链表分解成比较头节点 合并剩下的部分。能两种解法都写出来的人说明他对链表这种数据结构的理解不是死记硬背而是真正掌握了两种组织逻辑。这也是为什么我在指导别人刷题时会特意要求他们同一道题用两种方法实现。如果你只能写出其中一种建议花点时间把另一种也练熟这对后续理解归并排序、分治思想都有帮助。1.3 后续难题拼图中不可缺的一块合并两个有序链表是不少进阶题的地基。比如 LeetCode 23 合并 K 个升序链表一种朴素做法就是把两个有序链表的合并逻辑反复调用两两合并直到只剩一条链。再比如 LeetCode 148 排序链表核心思路就是在链表上做归并排序而 merge 环节本质上就是这道题。如果你现在把这道题的两个版本彻底弄透后面遇到这些题会轻松很多。所以别把这道题当一道孤立的小题来刷。它表面上是怎么合并底层其实是多路归并分治合并指针移动这些通用能力的缩影。地基打得稳后面盖楼才不慌。2. 迭代解法哨兵节点与指针推进的完整拆解2.1 不用 dummy 节点会遇到的麻烦先看一个最常见的直觉版写法不引入任何额外节点def mergeTwoLists(l1, l2): if not l1: return l2 if not l2: return l1 if l1.val l2.val: head l1 l1 l1.next else: head l2 l2 l2.next cur head 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 head这段代码能跑通但你发现问题了吗头节点的选择被单独拆成了两个分支需要先比较一次才能决定 head 指向谁。这还不是最麻烦的最麻烦的是合并过程中我们把head和cur分开管理一旦链表更长、情况更复杂这种写法很容易在某个分支里漏掉指针更新。如果用 C 语言学过带头结点的单链表你会发现 LeetCode 上给的链表结构是不带头结点的也就是说第一个节点的前一个位置并不存在一个额外的节点。为了简化头节点的处理一个非常自然的思路就产生了我们自己临时造一个虚拟头结点出来。2.2 哨兵节点临时加出来的虚拟头结点哨兵节点dummy node的思路可以用一个生活类比解释。想象银行排队两个队伍的客户要合到一条队伍里但你不知道第一个进来的人是谁。这时候最简单的办法是在窗口前面放一把空椅子每来一个人就坐到最后面最后把空椅子撤掉剩下的队伍就是完整有序的。dummy 节点就是那把空椅子。它在合并过程中始终充当已合并链表的虚拟头真正要返回的头节点是dummy.next。这样带来的好处非常明显循环内部不需要区分第一次还是第 N 次合并所有节点都一视同仁地接在cur.next后面代码逻辑得到了极大简化。加上 dummy 之后代码从头到尾只有一个主循环循环外面不需要任何分支去处理头节点选择。这是我在实际面试中非常推荐的写法因为它不容易出错也容易跟面试官讲清楚每一步在做什么。2.3 完整代码与逐行运行逻辑下面是加入了哨兵节点之后的迭代版本我用 LeetCode 的ListNode结构来写class ListNode: def __init__(self, val0, nextNone): self.val val self.next next class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) - ListNode: dummy ListNode(-1) 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逐行理解一下dummy ListNode(-1)创建虚拟头结点值随便填重点是next指针。cur dummycur始终指向已合并链表的最后一个节点。while l1 and l2只要两个链表都还有节点就继续比较。这里用and而不是or是有讲究的一旦某个链表走完了后面的节点不需要再比较直接整段接上即可。if l1.val l2.val取较小的节点接到当前链尾。cur cur.next这一步是新手最容易漏的。每接入一个新节点cur 必须后移否则下一次cur.next ...会把刚接上的节点覆盖掉。循环结束后的cur.next l1 if l1 else l2处理多余部分。两个链表长度不可能完全相等总有一段是剩余的而剩余段本身就是有序的所以直接整段接上。return dummy.next跳过虚拟头返回真正的合并结果。这段代码的逻辑可以用循环不变量来总结在每次循环执行前dummy.next到cur之间的节点构成一个升序链表且cur是该链表的尾节点。整个 while 循环反复执行取较小节点接到尾部 cur 后移这两个动作循环结束后再处理剩余段。2.4 等值节点的处理与稳定性问题还有一个细节值得单独说当l1.val l2.val时上面的代码会走else分支也就是把l2的节点接入。这在 LeetCode 的判定下没有问题因为题目只要求最终结果有序不要求相等元素的相对顺序保持不变。但如果你在面试中主动提到稳定性这件事会是一个明显的加分项。如果把判断条件写成if l1.val l2.val那么相等时优先取l1的节点这样原链表中的相对顺序在合并后得以保留也就是所谓的稳定合并。这在某些场景下比如链表里每个节点还携带其他排序字段是有实际意义的。面试时能主动说出这个区别说明你不是只会背代码而是真理解了比较逻辑的影响。3. 递归解法把合并问题拆成子问题3.1 链表天然是递归结构的三种观察方式递归解法的核心前提是链表本身就是一种递归定义的数据结构。这句话可以从三个角度观察从定义看一个节点由val和指向下一个节点的next组成而next指向的又是由同样结构组成的子链表。从遍历看对链表的任何操作都可以写成处理当前节点 处理剩余链表这天然对应递归的函数调用。从拆分看合并两个链表总能转化为比较两个头节点选较小的那个然后继续合并剩下的部分。一旦接受了这个视角递归解法就不再神秘它只是把一个规模为 n 的问题缩小成了规模为 n-1 的子问题。3.2 递归代码与递推关系拆解递归版本的代码非常简洁class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) - ListNode: if not l1: return l2 if not l2: return l1 if l1.val l2.val: l1.next self.mergeTwoLists(l1.next, l2) return l1 else: l2.next self.mergeTwoLists(l1, l2.next) return l2这段代码的递推关系可以这样理解mergeTwoLists(l1, l2)返回值是合并 l1 和 l2 之后的新链表头节点。如果l1.val更小那么新链表的头节点一定是l1剩下要做的事情就是让l1.next指向mergeTwoLists(l1.next, l2)的结果。注意这里l1.next没有被提前保存因为下一轮递归会用到当前的l1.next作为参数。如果你对链表操作不熟可以先在草稿上画出两个链表然后跟着递归过程走一遍。递归基base case也非常清晰如果l1为空直接返回l2剩余部分如果l2为空直接返回l1剩余部分。这两行代码同时处理了空链表的边界情况而且不会出现访问空指针异常的隐患。3.3 递归如何组装结果很多人对递归犯愁不是不会写递推关系而是想不明白返回值到底怎么被接上。这里可以换个角度不要试图跟踪每一层递归只需要相信函数返回值就是合并后的链头。当较小节点确定后把它的next指向子问题的返回值再把当前节点返回给上一层结果就自然组装起来了。我用一个生活类比你在整理两副牌规则是每次拿较小的那张放上面。递归的想法是我不一次性整理完而是先看最上面两张牌谁小把它放一边然后对剩下的牌执行同一个整理动作。一层层深入直到某一副牌空了把另一副整体放上然后逐层返回。这个过程的还原顺序恰好是从尾部向头部反向进行的最终的返回值就是整副牌最上面那张。理解了这个组装过程递归链表题基本就通了。3.4 递归的空间代价与 Python 的递归深度上限递归版本写起来漂亮但有一个必须正视的代价空间复杂度不是 O(1)而是 O(nm)。因为每次递归调用都会在调用栈上占用一层空间最坏情况下比如两个链表交替取值递归深度会达到两个链表长度之和。在 Python 环境里尤其需要小心。CPython 默认的递归深度限制是 1000 层一旦链表长度加起来接近这个数就会触发RecursionError。LeetCode 的测试用例里通常不会出现这么长的链表但本地测试时你可以自己构造一个 2000 节点的链表试试大概率会看到报错。所以我在实际刷题时通常优先写迭代版本递归版本用于理解思路和面试时展示第二种解法。如果你确实需要用递归处理很长的链表可以先把 Python 的递归上限调高但那样做在工程上并不稳妥还是建议改成迭代。4. 边界条件、复杂度与测试用例设计4.1 边界情况逐一过电影合并两个有序链表的边界情况没有特别刁钻的但每一项都值得单独验证两个链表都为空迭代版本中 while 循环不执行cur.next l1 if l1 else l2得到 Nonedummy.next也是 None返回空链表。递归版本两个if not都命中直接返回 None。一个链表为空另一个非空迭代版本直接把非空链表整体返回递归版本直接返回非空链表。这时的处理效率是 O(1)因为不需要任何遍历。两个链表都只有一个节点比较一次后cur.next指向较小节点循环退出剩余那段恰好是另一个单节点链表接上即可。两个链表一个长一个短短链表先耗尽退出循环后把长链表的剩余部分整体接上。这里如果有节点遗漏多半是因为循环退出后没有执行cur.next l1 if l1 else l2这行代码。我在看别人代码时发现一个高频毛病很多人会把while l1 and l2误写成while l1 or l2。一旦用 or循环体内就必然会出现某个链已经是 None 但还在访问l1.val的问题要么提前加一堆判空分支要么直接抛异常。这个细节非常小但在面试中特别能检验一个人对指针状态的理解。4.2 复杂度的两种口径对比这道题的时间复杂度无论用哪种解法都是 O(nm)其中 n 和 m 分别是两个链表的长度。因为每个节点都需要被访问一次来参与比较和连接这个下界是无法突破的。真正拉开差距的是空间复杂度下面这张表可以直接拿去给面试官讲对比维度迭代版本递归版本空间复杂度O(1)只用常数个指针O(nm)递归栈深度栈溢出风险无链表较长时存在代码行数约 10 行约 7 行理解门槛需要维护循环不变量需要理解递推关系面试推荐顺序先讲迭代可作为补充方案时间上还有一个细节值得聊虽然复杂度同阶但迭代版本和递归版本的实际运行时长会有差异。递归涉及函数调用栈的压入和弹出常数开销更大。我自己在本地用 10 万个节点的链表测过一次迭代版本快了大约 12%。这种差距在 LeetCode 的测试数据量下很难体现但在嵌入式或性能敏感场景中能写迭代就不要用递归。4.3 本地测试用例怎么设计LeetCode 会帮你覆盖大部分 case但为了把一套代码调稳我很推荐在本地写一个简单的测试函数。不需要引入测试框架用 Python 内置的assert就够了def build_linked_list(values): dummy ListNode(-1) cur dummy for v in values: cur.next ListNode(v) cur cur.next return dummy.next def linked_list_to_list(head): result [] while head: result.append(head.val) head head.next return result def test_merge(): s Solution() assert linked_list_to_list(s.mergeTwoLists(build_linked_list([]), build_linked_list([]))) [] assert linked_list_to_list(s.mergeTwoLists(build_linked_list([1, 3, 5]), build_linked_list([]))) [1, 3, 5] assert linked_list_to_list(s.mergeTwoLists(build_linked_list([]), build_linked_list([2, 4, 6]))) [2, 4, 6] assert linked_list_to_list(s.mergeTwoLists(build_linked_list([1, 2, 4]), build_linked_list([1, 3, 4]))) [1, 1, 2, 3, 4, 4] assert linked_list_to_list(s.mergeTwoLists(build_linked_list([1, 3]), build_linked_list([2, 4, 5, 6]))) [1, 2, 3, 4, 5, 6] test_merge()这里第 4 条故意用了两个都包含值 1 的链表用来验证相等元素能否正确处理。第 5 条验证长短不一的场景。把这些用例跑过一遍我才能放心把这个解法交出去。如果你还有余力可以再加一个 1000 节点的随机数对拍测试把一个正确但慢的版本用来对照能进一步减少隐藏 bug。5. 从这道题延伸出去链表题型的通用方法论5.1 合并 K 个升序链表从两两合并到优先队列合并两个链表的逻辑一旦吃透LeetCode 23 合并 K 个升序链表就只剩工程组合问题了。最直观的做法是顺序两两合并第一轮用第 1 条链和第 2 条链合并结果再和第 3 条链合并以此类推。这种做法的复杂度是 O(k²n) 量级k 越大越吃亏因为前面合并好的结果会被重复遍历多次。更优的方案是使用优先队列堆把 K 个链表的头节点全部入堆每次弹出最小的节点接入结果链表同时把该节点的下一个节点补入堆中。这样整体复杂度是 O(N log k)其中 N 是节点总数。这个思路本质上还是每次取最小的那个节点和合并两个链表的核心逻辑完全一致只是比较范围从两个头节点扩展到了 K 个头节点。5.2 排序链表归并思想的另一处应用LeetCode 148 排序链表是另一个非常典型的延伸题。它要求对链表排序而且时间复杂度要求 O(n log n)。随便套用一个数组排序算法是做不到的因为链表不支持 O(1) 随机访问。常规解法就是归并排序先用快慢指针找到链表的中点拆成两条半长链表递归排序后再用合并两个有序链表的逻辑把它们合起来。当你写出merge那一步时会发现它就是本文这道题的解。我曾经跟朋友开玩笑说合并两个有序链表就像螺丝刀光用也不起眼但配上拆链表、找中点这些工具就能组装出排序链表这种更复杂的机器。很多题目之间的连接就是这样你今天解的一道 easy 题可能正在给明天的 hard 题铺路。5.3 链表题的三个通用心法与我踩过的坑总结一下链表题最常见也最好用的心法就是三个dummy 节点省去头节点分支、双指针推进避免覆盖、递归实现则优先保证返回值的语义清晰。合并两个有序链表恰好同时用上了前两个又用递归展示了第三个。能把这三点想透很多看似不同的链表题都会变得有章法可循。最后分享几个我实际写这道题时踩过的坑希望你能绕开忘记cur cur.next。这是最常见的死循环根源。每接入一个节点cur 必须后移否则每次都把新节点接到同一个位置链表结构就乱了。返回值弄错。迭代版本应该返回dummy.next不是cur也不是dummy本身。dummy是虚拟头把它返回出去会让结果链表多一个多余节点。递归版本里没有处理好l1.next的改写。很多人会先写一行temp l1.next后面的递归却忘了用导致返回的链表断掉或者形成环。其实直接写l1.next self.mergeTwoLists(l1.next, l2)是最不容易错的写法。本地测试时构造链表稍不注意就容易写出带循环的测试数据。构造链表时严格要求每次 new 一个节点并且最后让尾节点的next指向 None。我的习惯是每写完一道链表题都在草稿纸上把三个指针的移动轨迹完整画一遍确认每一步的指向都符合预期。这个习惯看着笨但真的能帮你发现很多只在脑子里过一遍会被忽略的问题。合并两个有序链表这道题代码很短值得咀嚼的细节却不少。把它彻底吃透再去看合并 K 个链表和排序链表你会感觉整个人都顺畅了不少。