如果你刷过力扣hot100应该会对第22题“合并两个有序链表”不陌生。说实话我第一次写这题时循环里少写了一行指针移动测试用例直接死循环对着屏幕愣了半天。后来刷多了才发现这题是链表操作基本功的浓缩双指针怎么走、哨兵节点怎么用、边界怎么收尾全在这几行代码里。今天我把迭代和递归两个主流解法连同我在面试和带新人时踩过的坑一起整理出来适合准备面试的人、正在刷hot100链表题的新人也适合想快速复习链表基础的老玩家。1. 这道题为什么值得认真刷1.1 题目到底是什么“合并两个有序链表”的题面很干净给你两个升序排列的单链表头节点 l1 和 l2要求把它们合并成一个新的升序链表并返回新链表的头节点。我见过不少网友第一次看题时的反应这有什么好说的把两个链表的节点全遍历一遍排序一下不就行了这样想也没错但如果你真在面试里这么做大概率会被追问一句那空间复杂度是多少如果题目要求不额外开辟节点数组只通过调整指针完成合并你怎么办这就是链表的特别之处。它不像数组那样可以直接按下标访问也不像普通对象那样可以随意复制。链表的最小单位是节点每个节点里存着 val 和 next 指针。合并两个有序链表本质上是把两个已有的节点串重新“穿线”让它们按大小顺序组成一个新的链条。你可以在不改动节点值的前提下通过修改 next 指针完成整个合并过程这就是这道题最核心的考察点。题目给出的约束也很常规两个链表的节点数范围是 0 到 50节点值范围是 -100 到 100两个链表各自已经是升序。注意“各自有序”这个前提很重要它意味着我们不需要做全局排序只需要做一次归并式的大小比较。1.2 面试里它为什么高频从面试角度看这道题几乎是链表基本功的试金石。题目短但考察点非常集中你有没有真正理解“节点是对象不是值”你清不清楚指针移动的时机你能不能处理一长一短、一空一非空这类边界情况。这些都是链表题目最常见的失分点偏偏这道题全部包含。我之前有位工程师朋友去某公司面试第一轮算法题就是这道原题连变形都没加。他思路其实是对的双指针比较谁小接谁结果最后忘了把剩余链表整段接上测试用例里两个链表长度不一致输出直接丢了一半数据。面试官心平气和地提醒了一句“你还有一条链表没走完”他这才反应过来。这种翻车方式我见得太多了代码量越少细节越容易漏。另外这道题还是很多难题的“零件”。光我知道的就有合并 K 个有序链表、链表排序归并排序的 merge 阶段就是它、两个链表相加、排序链表去重等。刷完这一题等于为后面一批题打好了地基。它难度不高性价比却极高这也是它能长期留在 hot100 里的原因。2. 迭代解法把思路翻译成代码2.1 核心思路哨兵节点与双指针合并两个有序链表的迭代思路可以用一句话说明同时遍历两个链表谁小就先接谁直到其中一个链表走完再把剩下的整段接上。但短语落到代码里会夹带几个细节。第一个细节就是头节点的处理。如果你脑子一热想“先在两个头里选出较小的那个作为结果头”后面就要为“这是第一次接入”写一堆判断。更优雅的做法是引入一个哨兵节点也叫 dummy 节点。这个节点不参与业务数据它的作用只是让结果链表在为空时也能有一个统一的尾指针。我经常打一个比方把合并链表想象成串珠子哨兵节点就是临时挂钩。珠子还没串上时cur 指针是挂在挂钩上的。每选定一个小珠子就把它挂到 cur.next 上然后 cur 跟着前进。所有珠子串完之后把挂钩去掉返回挂钩后面的整串。这样头节点就永远不会变成特殊分支。第二个细节是双指针的推进。初始时一个指针指向 l1 头一个指向 l2 头cur 指向当前结果链表的尾部。每一轮比较两个指针指向的节点值把较小的那个接到 cur.next 上然后让对应的链表指针往后走一步。注意无论谁被接上去cur 都要往后走一步。如果少了这一步下一次接入会把新节点接在旧位置轻则覆盖连接重则形成环死循环就这么来的。很多初学者容易把注意力全放在“谁大谁小”上反而忘了维护结果链表自己的尾指针。第三个细节是循环退出后的收尾。循环条件通常写成 while l1 and l2意思是只要有一方为空就退出。此时另一方可能还剩下一串节点如果还去一个一个遍历再接虽然也能做但没必要。因为剩余链表本身有序而且所有剩余节点都大于或者等于已经合并完成的最大值直接让 cur.next 指向它即可。这一步是迭代版能保持 O(m n) 时间复杂度而不额外浪费遍历的关键。2.2 迭代代码与分步说明很多语言的实现语法不同但骨架完全一样。我用 Python 写一版最直观的实现class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def mergeTwoLists(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这段代码很短但每一行都值得认真理解。当执行 cur.next l1 时做的只是让结果链表的尾部指向 l1 当前节点并没有复制节点。此时 l1 的头节点相当于从原链表里被“摘走”了紧接着执行 l1 l1.next是为了让原链表的遍历光标往后移。如果漏掉这一行下一次 while 判断时 l1 还是同一个节点反复把同一个节点接进去链表就会变成环。我在本地测试的时候常用的用例是这两条链表1→3→5 和 2→4。合并过程逐轮展开是这样的第一轮l1.val1l2.val21 更小接到 cur 后面l1 走到 3cur 走到刚接上的 1。第二轮3 和 2 比较2 更小接到 1 后面l2 走到 4cur 到 2。第三轮3 和 4 比较3 更小l1 到 5。第四轮5 和 4 比较4 更小l2 走完变成 None。循环退出此时 l1 还剩一个 5直接让 cur.next 指向 5。最终 1→2→3→4→5。如果你把注意力放在 cur 的移动轨迹上会发现它就是新链表不断生长的“结尾指针”永远指向最后一个已经被接好的节点。理解了这个代码就活了。这里还有一个很容易被面试官追问的细节当两个节点值相等时先接哪个我的写法是 if l1.val l2.val先接 l1。这样做的一个额外好处是在归并排序的 merge 阶段可以保持相同关键字元素的相对顺序也就是所谓的稳定性。题目本身没有明确要求稳定性但养成先接第一条链表的习惯没有坏处。2.3 复杂度与空链表边界时间上两个链表每个节点最多被比较一次、被接入一次所以时间复杂度是 O(m n)。空间上整个过程只定义了一个 dummy 节点和几个指针没有额外分配任何链表节点所以空间复杂度是 O(1)。在实际运行时这个版本表现非常稳定。即使我本地构造两个长度各为几万节点的链表来测循环也能一路跑完没有栈溢出、没有内存暴涨运行时间符合线性预期。边界情况也不用额外加判断。如果 l1 是 Nonewhile 循环根本进不去直接走收尾逻辑返回 l2。如果两个都是 None收尾逻辑返回 None也完全合理。这套写法的好处在于空链表不是被“特判”掉的而是被正常流程自然覆盖的。如果你在面试里写了额外的 if not l1 or not l2 分支倒也不是错但面试官可能会觉得你边界判断多到没必要。标准写法本身已经包含了这层安全垫不用画蛇添足。3. 递归解法更短的代码更大的代价3.1 递归的切入角度把“合并”看作子问题迭代版适合工程落地递归版则更贴近问题本身的结构。你可以把“合并两个有序链表”想成一个递归定义如果 l1 为空答案就是 l2。如果 l2 为空答案就是 l1。如果两个都非空比较头节点值。假设 l1.val 更小那么合并结果的头部就是 l1它后面接的应该是“l1 的下一个节点和整个 l2 合并后的结果”。第三句话翻译成代码就是l1.next mergeTwoLists(l1.next, l2)。每一次递归都会吃掉当前更小的头节点链表长度不断缩短直到某一方为空触发出口。我刚开始学递归的时候总想手动模拟每一步入栈出栈结果脑袋越想越乱。后来发现一个更实用的方法你自己只管“当前层”做什么至于“下一层”返回什么直接信任函数本身的定义就好。你只需要确认下一层的输入是长度更短的子问题它一定能返回排好序的链表头。只要递归出口写对了后面的结果是自然成立的。这种“信任递归”的思路也是面试官想听到的。比起背代码能清晰说出“我把规模缩小了子问题结构和原问题一样出口条件明确”才是真正的理解。3.2 递归实现与风险点递归版的标准代码非常短我经常用下面这版def mergeTwoLists(l1: ListNode, l2: ListNode) - ListNode: # 递归出口某一方为空直接返回另一方 if not l1: return l2 if not l2: return l1 if l1.val l2.val: # l1 作为头节点剩余部分交给递归 l1.next mergeTwoLists(l1.next, l2) return l1 else: # 相等时这里默认选 l2不影响正确性 l2.next mergeTwoLists(l1, l2.next) return l2这段代码写出来非常漂亮但我建议你至少完整跑过一遍再上考场。我在模拟面试里帮一个朋友 review 这段代码时发现他写成了 if l1.val l2.val也就是相等时优先选 l1。他后来自己也意识到等于和小于在这里都能正常工作但面试时如果不能解释清楚“为什么等价”容易被追问到卡壳。两个明显风险点要记牢。第一递归版的空间复杂度不是 O(1)而是 O(m n)。因为每次递归都会占用一层调用栈最坏情况下递归深度等于两个链表的总节点数。面试中如果面试官特别看重内存用量你应该主动说清楚这个区别顺便表示“如果对空间有严格要求我可以改成迭代版”这是很加分的回答。第二不要拿递归版去处理特别长的链表。比如两个链表合起来有上万节点Python 默认递归深度上限大概是一千层直接抛 RecursionError。C 和 Java 虽然没有这个明确的层数限制但调用栈内存终究有限深度过万照样栈溢出。笔试测试数据通常很短但如果你想把代码用在真实场景里还是迭代版更稳妥。我的个人习惯是面试时先讲迭代版因为它稳适合工程等面试官追问“还有没有其他思路”再补充递归版展示你对递归边界的理解和空间复杂度的权衡。两个版本互为补充不是替代码而是互相印证。4. 常见变形题这些题目考的是同一件事4.1 从两个到 K 个合并 K 个有序链表合并两个有序链表最常见的进阶就是合并 K 个有序链表。输入变成链表数组要求把它们统一合并成一个有序链表。我见过不少人第一反应是写一个两两合并的循环def mergeKLists(lists: list[ListNode]) - ListNode: ans None for link in lists: ans mergeTwoLists(ans, link) return ans这段代码理论上没错但复杂度不理想。假设有 K 个链表每个平均 n 个节点第一次合并 O(n)第二次 O(2n)第三次 O(3n)最后一次 O(kn)总复杂度会膨胀到 O(k^2 n)。如果链表数量多尤其每个链表还很长这个写法在压力测试下会非常难看。更常见的优化方案是分治合并。先把相邻的两个链表两两合并得到大约一半数量的新链表再继续两两合并像归并排序那样分层处理。每一层要处理的总节点数都是 O(kn)一共 log k 层所以总复杂度是 O(kn log k)空间开销可以控制在 O(1)如果用递归实现则会有 O(log k) 的调用栈。还有一个面试高频方案是用优先队列也就是最小堆。把 K 个链表的头节点全部放进堆里每次弹出最小的节点接到结果链尾再把这个节点的 next 压回堆里直到堆空。这个方案的时间复杂度同样是 O(kn log k)胜在思路直观尤其适合引出“多路归并”和“外部排序”这些话题。我在面试别人时如果能从合并两个链表一路聊到合并 K 个链表、再聊到多路归并基本就能判定这个候选人对归并思想理解得比较透。4.2 更多变式排序、相加、去重除了 K 路归并合并两个有序链表的思路还会以各种形式出现在其他题目里。第一个是排序链表。标准做法是自顶向下归并排序先找到链表中间节点切成两半分别排序然后再把两条有序子链表合并起来。你发现没有最后一步的 merge 函数本质上就是第22题的迭代版。换句话说你刷完这一题归并排序的一半已经握在手里了剩下的只是“找中间节点切分”的技巧。第二个是两数相加。两个链表逆序存储数字要求按位相加后输出新链表。它同样需要同时遍历两个链表还要用 carry 进位变量协调相加逻辑。如果你已经熟练于双指针维护多个链表这题只是把“比较大小”换成“加法运算”。第三个是删除排序链表中的重复元素。有序链表里去重核心也离不开“一个指针控制当前遍历位置另一个指针负责调整 next 指向”。它的操作风格和合并题有很多相似的地方都在处理“什么时候该动 next、什么时候该动 cur”。第四个是两个链表的第一个公共节点。这个题需要同步移动双指针很多人会和合并题混淆但共同之处是它们都很依赖对指针推进时机的精确把握。我建议你把“合并两个有序链表”当作链表双指针类题目的入口题。刷熟它后面遇到这些变式时你会有种“代码骨架我都见过只是换了业务逻辑”的感觉。5. 常见错误与排查速查表5.1 高频翻车点与修正对照表链表题最大的痛苦不是没有思路而是细节写错却不容易发现。我把常见的错误写法整理成了一张对照表刷题遇到问题时直接按表排查。错误写法表现原因正确做法while l1.next and l2.next合并结果少了一部分循环条件限定过严头节点比较被跳过用 while l1 and l2让每个非空节点都有机会被比较while l1 or l2 但内部不判空报空指针或 NoneType 没有 val退出条件过宽进入循环后可能有一方已为空用 while l1 and l2退出后统一收尾忘记写 cur cur.next死循环链表成环结果链表尾部从未前进每次接入节点后必须让 cur 后移最后 return cur返回了结果链表尾部甚至 None混淆了“遍历指针”和“头节点引用”返回 dummy.next递归出口只写 if not l1 return l2某一方先为空时逻辑不完整只覆盖了一种空的情况两个独立出口not l1 返回 l2not l2 返回 l1值相等时处理逻辑不统一结果正确但面试解释不清没意识到小于等于和小于在这题等价选一种写法并明确说明理由这里面最经典的是 return cur。我见过不少初学者把 cur 当结果头返回结果输出一个孤零零的尾节点或者直接输出 None。原因就在于他们只记住了“cur 是移动指针”忘记了真正的头节点是 dummy.next。这个失误在面试里一出现基本就是白送一题。还有一个小细节值得提醒如果你在本地测试时发现输出链表里有循环最简单的排查方法就是检查是否有哪行代码把同一个节点接进去了两次或者 cur 没有前进。死循环绝大多数都出自这两个原因。5.2 本地调试链表的两个小工具链表题目调试起来比数组麻烦因为语法里看不到“整个链表”只能看到一个个散落节点。我强烈建议你在本地准备好一个小工具函数把链表转成普通数组打印出来一目了然。def to_list(head): res [] while head: res.append(head.val) head head.next return res然后在测试时构造两条很容易跟踪的小链表比如 1→3→5 和 2→3→4合并结束后调用 to_list(result)立刻能看到顺序对不对、有没有丢节点。这个方法比盯着代码发呆高效太多。另一个我觉得很管用的技巧是“小规模全排列测试”。构造两个只含少数节点的链表比如 [1,2] 和 [1,3]把所有可能的插入顺序都跑一遍再和预期结果对比。链表长度短手动验证成本低却能覆盖大多数顺序组合。我用这个方法抓出过自己不少边界问题尤其是在相等值连续出现的情况里。6. 这道题教会我的做题方法论6.1 画图比看代码更重要链表题光靠脑子想不如画图来得实在。我在给新人讲这道题时总是要求他们在纸上先画出两条链表然后用一支笔模拟 cur 指针。谁小谁被接走指针怎么挪最后剩下的一串怎么挂上去。整个过程不超过三分钟但一旦能画明白代码就是翻译。很多人写合并链表卡住通常不是不懂“谁小放谁”而是不知道头节点怎么处理、剩余部分怎么接。画图能最先暴露这两个盲点你会直观看到如果不引入 dummy 节点第一次接入和后续接入的逻辑就会不一致如果收尾时不做整段拼接就得多写一个 while 循环去逐个处理剩余节点。我自己的习惯是把这类链表题的分步图留在笔记本里。刷题时先画一遍写代码时照着图形翻译写完后用 to_list 验证。这套流程下来出错率比我硬写代码低得多。6.2 刷一题省十题的归类习惯刷题最忌讳孤立地背答案。我的习惯是每刷完一题记录它可以用在哪些同类题里。第22题至少有三个延伸方向结构延伸合并两个链表 → 合并 K 个链表 → 多路归并 → 外部排序。顺序延伸升序合并 → 降序合并 → 排序链表中的 merge 步骤。指针技巧延伸双指针遍历 → 快慢指针 → 带步长的多指针控制。这样每次在 hot100 里再遇到新的链表题我第一反应不是“这题我没见过”而是“它和合并两个有序链表有什么共同点差异在哪”。做过一段时间后你会发现刷题速度明显变快因为很多题之间本来就有不同层次的关联。最后分享一个小技巧。在面试时被问到“合并两个有序链表”不要急着写代码。先问面试官两个问题链表是否允许原地修改如果有多个相等值合并后是否要求保持原有相对顺序这两个问题一方面能让面试官觉得你思路严密另一方面也确实影响代码怎么写。面试官平时最怕的就是候选人上来就闷头写代码边界全靠猜写完还不解释。合并两个有序链表这道题在我看来是链表入门的试金石也是后续很多复杂问题的积木。把它刷透比盲目刷十几道同类型题目有用得多。用点心把迭代版和递归版都写到熟练再把变形题过一遍你会发现链表题的主干越来越清晰。