合并两个有序链表详解：迭代、递归与复杂度分析-北京尧图网络

不用被“合并两个有序链表”这种朴素题目劝退它在力扣上是第21题地位却很特别——既是链表题里的“hello world”又是后续很多复杂题目的积木。许多人刷到这题时觉得简单扫一眼就翻过去了结果到“合并K个升序链表”“两两交换链表中的节点”甚至“排序链表”时卡住回头才发现是这道基础题的理解不够扎实。我自己最早也是草草写完迭代版就完事直到在面试里被问“递归版怎么写递归的调用栈你画得出来吗”才意识到这题值得认真拆一遍。这篇文章会把第21题从头到尾做一个完整的拆解从题目到底考查什么到迭代法和递归法两套解法的推导过程与代码实现再到复杂度分析、面试延伸题和实战中容易踩的坑。内容尽量照顾两种读者——刚接触链表的新手可以按步骤慢慢跟有经验的也可以直接跳到后面看边界条件和变种思路。1. 先拆题这道题真正在考什么1.1 题目本身的描述先把原题说清楚。给定两个升序排列的链表比如l1 1 - 2 - 4和l2 1 - 3 - 4要求把它们合并成一个新的升序链表并且新链表仍然保持升序最终结果是1 - 1 - 2 - 3 - 4 - 4。题目给的是节点定义通常是这样的结构class ListNode: def __init__(self, val0, nextNone): self.val val self.next next链表的头节点代表整个链表的起始位置每个节点只知道自己存的值和下一个节点是谁这种线性结构决定了我们只能从前往后遍历不能像数组那样随机访问。1.2 题面背后的三个核心考点这题表面是“合并”实际上在考察三个基本能力第一个对链表指针移动的掌控。和数组题不同链表没有下标你能做的就是通过next指针一步一步走。很多新手在合并时容易把指针指乱搞出环或者丢节点根源就是对“谁动了、谁没动”缺乏清晰认知。第二个对“哑节点”这个技巧的运用。这是链表题里极其常用的一招。新链表需要一个起点但一开始这个起点是空的直接拿l1或l2的头节点当新链表的头写起来会非常别扭因为你要单独处理“第一次选谁当头”。哑节点dummy node就是先造一个占位的空节点最后返回dummy.next让整个合并过程变得统一流畅。第三个边界条件的完备性。两个链表可能一个为空、可能两个都为空、可能在合并过程中一个先走完。这些情况如果不提前想清楚代码很容易在运行时抛空指针异常。1.3 这道题为什么值得反复刷《21. 合并两个有序链表》在力扣上是“简单”难度但它的价值不在于难度而在于它是一系列高频题的共同基础。力扣第23题“合并K个升序链表”就是本题的N路扩展第148题“排序链表”中间步骤需要用到两个有序链表的合并第86题“分隔链表”虽然思路不同但对指针的精细操作要求完全一致。把这题吃透后面遇到这些题时会顺畅很多。我个人的建议是这题至少要能写出迭代版和递归版两种解法并且能在不看题解的情况下把两种思路完整推导一遍。这并不难但带来的回报很直接——面试中凡是涉及链表操作的问题核心都在于对指针和边界条件的把握而这题恰好把这两点练得最充分。2. 迭代解法把每一步指针移动都安排明白2.1 核心思路谁小谁先走迭代法的思路用一句话就能说清同时遍历两个链表比较当前两个节点的值把值较小的那个接到结果链表上然后让对应链表的指针前进一步。重复这个过程直到某一个链表走完再把剩下的链表整体拼接上去。这个过程可以用排队来类比两个队伍的人已经按身高从低到高排好了现在要把他们合成一个队伍。每次看一眼两个队头的个子把矮的那个拉出来站到新队伍末尾然后看下一个。当其中一个队伍空了直接把另一个队伍剩下的人整个接上。2.2 用哑节点统一处理写代码前先想清楚一个问题新链表的头从哪里来一种朴素做法是先单独比较l1和l2的头节点把较小的那个作为新链表的头然后进入循环。这能用但代码会多一个分支而且逻辑上不够统一。更干净的方式是使用哑节点dummy ListNode(-1) cur dummydummy节点本身不存有效数据它的作用只是给新链表一个起始的挂载点。合并过程中cur始终指向新链表的最后一个节点每次接入一个新节点cur就移动到新节点上。最终返回dummy.next就能拿到真正的新链表头。这一步初看有点绕但它是链表题最常见的统一化技巧。后面写“合并K个链表”的优先级队列解法时哑节点同样会让代码简洁很多。2.3 完整代码Python版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这段代码短但每一行都有讲究。while l1 and l2保证了比较的安全性——只要有一个链表为空循环就结束不会出现空指针访问。if l1.val l2.val这里用而不是是为了保证稳定性——如果两个值相等优先取l1的节点这属于细节层面的严谨性面试时说出来是加分项。最后那句cur.next l1 if l1 else l2是整个函数里最省心的一行它同时处理了三种情况l1为空、l2为空、两者都为空。2.4 再给一个Java版本和C版本class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy new ListNode(0); ListNode cur dummy; while (l1 ! null l2 ! null) { if (l1.val l2.val) { cur.next l1; l1 l1.next; } else { cur.next l2; l2 l2.next; } cur cur.next; } cur.next l1 ! null ? l1 : l2; return dummy.next; } }class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* dummy new ListNode(0); ListNode* cur dummy; while (l1 ! nullptr l2 ! nullptr) { if (l1-val l2-val) { cur-next l1; l1 l1-next; } else { cur-next l2; l2 l2-next; } cur cur-next; } cur-next l1 ! nullptr ? l1 : l2; return dummy-next; } };三种语言逻辑完全一致唯一要注意的是C里new出来的dummy节点需要手动释放内存不过在实际刷题环境中通常不追究这一点面试时提一句“工程上要注意delete”反而显得有经验。2.5 边界条件逐个过一遍写链表题最怕的就是边界条件想不全。我把这题的边界情况列出来你可以对着检查自己的代码场景l1l2预期结果两者都为空nullnullnulll1为空null1-21-2l2为空1-2null1-2等长1-32-41-2-3-4一个链表先走完1-2-31-4-5-61-1-2-3-4-5-6相等值交错1-2-31-2-31-1-2-2-3-3细看会发现只要while条件正确、最后一步拼接代码写对了上面所有情况都能覆盖到。这也是为什么我说哑节点加循环加尾部拼接这个模式是链表合并题的标准答案——它天然免疫了大部分边界问题。3. 递归解法把大问题切成同构的小问题3.1 递归的思考方式如果说迭代是“一步一步走”递归就是“我只需要解决当前这一步剩下的交给同样的规则”。对于合并两个链表来说定义merge(l1, l2)为“合并两个链表并返回新链表的头节点”那么这一步的操作其实只有两种可能如果l1.val l2.val新链表的头应该是l1而l1.next之后的部分和l2需要按同样的规则继续合并否则新链表的头是l2l1和l2.next继续合并。可以看到每一次递归都在缩小问题的规模——其中一个链表的节点数量减少了。递归的终止条件也很自然当l1为空时直接返回l2当l2为空时直接返回l1。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这段代码非常简洁。核心在于赋值语句l1.next self.mergeTwoLists(l1.next, l2)——它把原链表的一个节点“拆”下来让它的next指向后续合并的结果。每一步递归都会从l1或l2中取出一个节点作为返回值的头因此递归深度等于两个链表的总长度。3.3 递归过程可视化用例子走一遍拿l1 1 - 3、l2 2 - 4举例。调用merge(1-3, 2-4)时因为1 2所以取l1的1然后递归调用merge(3, 2-4)。在merge(3, 2-4)里3 2于是取l2的2递归调用merge(3, 4)。merge(3, 4)里3 4取l1的3递归调用merge(null, 4)。此时l1为空直接返回4。逐层回溯后拼出来的新链表就是1 - 2 - 3 - 4。推动过程可以用一个简单的括号表达merge(1-3, 2-4) 1 - merge(3, 2-4) 1 - 2 - merge(3, 4) 1 - 2 - 3 - merge(null, 4) 1 - 2 - 3 - 4看到没递归的每一步都没有动太多脑筋但这个“无脑信任递归函数本身”的能力恰恰是新手最需要练习的。3.4 递归版有什么优缺点递归版最大的优势是代码可读性高逻辑清晰不需要额外的哑节点也省去了手动控制循环变量的麻烦。面试时写递归容易给面试官留下思维清晰的印象。但递归也有代价。每层递归都会消耗调用栈空间如果链表特别长比如几十万个节点递归深度过大可能导致栈溢出。迭代版的空间复杂度是O(1)递归版则是O(n)其中n是两个链表的长度之和。后面会详细算这笔账。4. 复杂度分析面试官一问就能答上来4.1 时间复杂度O(m n)不管迭代还是递归每一步只处理一个节点。最坏情况下两个链表的所有节点都需要被遍历一次所以总的时间复杂度是O(m n)其中m和n分别是两个链表的长度。这里没有额外的比较开销每个节点的比较次数都是常数级因此这个复杂度是渐进最优的——毕竟合并两个有序链表至少需要查看所有节点才能确定最终顺序。4.2 空间复杂度两个版本差距明显迭代版额外只用了两个指针变量dummy和cur不随输入规模增长因此空间复杂度是O(1)。递归版每递归一层就占用一份栈帧栈帧数量等于两个链表总节点数因此空间复杂度是O(m n)。在面试中如果递归版能主动说出这个代价并补充一句“工程上倾向于用迭代避免栈溢出”面试官一般都会认可。4.3 关于稳定性假设两个链表中有相同值的节点比如l1 1 - 2 - 5l2 1 - 3。合并结果是1 - 1 - 2 - 3 - 5。问题来了两个值为1的节点谁在前我的迭代版和递归版都用了所以l1的1会排在l2的1前面。如果要求保持原始链表内的相对顺序即稳定性这个细节就很重要。大部分教科书算法都要求归并排序是稳定的本题的合并操作作为归并排序的核心子过程用也是一个好习惯。4.4 复杂度速查表维度迭代法递归法时间复杂度O(mn)O(mn)空间复杂度O(1)O(mn)代码可读性中等需要理解哑节点指针移动高逻辑直白边界处理需要严谨的循环条件终止条件很自然栈溢出风险无链表极长时有风险适合场景工程实现、超长链表面试演示、理解递归思想5. 力扣提交中的隐藏细节与调试经验5.1 你可能会写错的三个地方我在力扣上提交这题时差别不过几行代码但新手经常会在这几个地方翻车第一个忘记改cur指针。很多新手在把cur.next指向新节点后忘了把cur移动到新节点上结果新链表只有两个节点后面的全部丢失。这类问题肉眼很难看出需要逐步跟踪。一个实用建议是画三列“快照”一列是cur当前指向哪个节点一列是l1现在到哪了一列是l2现在到哪了。每次循环结束前检查三列是否和预期一致。第二个返回值写错。有人写return dummy有人写return cur这两个都不对。dummy是占位节点它的next才是真正的新链表头cur指向的是最后一个节点用它作为返回值只能拿到最后的节点。正确写法是return dummy.next。第三个边界条件不完整。比如把while l1 and l2错写成while l1.next and l2.next一旦链表只有一个节点就会空指针。或者少了最后拼接剩余链表的那句cur.next l1 if l1 else l2结果合并结果总是丢一半。建议在本地把上面那张边界条件表逐个测一遍。5.2 调试链表题的通用方法链表题在力扣上直接跑用例很方便出错时会显示节点的顺序但如果你只想看中间某一步的状态可以写一个辅助打印函数def print_list(head): res [] while head: res.append(str(head.val)) head head.next print( - .join(res))然后在循环里的关键位置调用它观察l1、l2、cur的变化。这个方法虽然简单粗糙但在排查指针问题时比盯着代码脑内模拟高效太多了尤其面对复杂链表题时。这里分享一个我自己的经验链表题出错时先别看输出结果而是先想“我的指针最后一次变化是在哪一行”。链表题的大部分bug都是指针指向了错误的位置而不是值比较出错。值比较错了输出可能是乱的但结构还在指针错了往往是丢链或者成环。分清这两类问题能少走很多弯路。5.3 本地运行完整示例在力扣里可以直接跑但如果想在本地调试要自己构造测试用例。一个小模板def build_list(arr): dummy ListNode(-1) cur dummy for val in arr: cur.next ListNode(val) cur cur.next return dummy.next l1 build_list([1, 2, 4]) l2 build_list([1, 3, 4]) merged Solution().mergeTwoLists(l1, l2) print_list(merged) # 期望输出1 - 1 - 2 - 3 - 4 - 4有了这个模板你可以把网上看到的测试用例直接复制进来验证不用每次都在力扣网页上反复提交。6. 延伸题从第21题到第23题合并K个有序链表6.1 最常见的面试追问面试官在你答完这题后九成会追问一句“如果现在不是两个链表而是K个链表呢”这就是力扣第23题“合并K个升序链表”的原型。你不要慌这道题的解法可以从第21题延伸出来。最暴力的方法是每次从K个头里找最小值时间复杂度O(K * total)。稍微聪明一点的是“两两合并”先合并链表1和2再把结果和链表3合并以此类推。这个做法每轮都要重新遍历已经合并出来的长链表总的时间开销并不理想。最推荐的方案是使用最小堆或者优先队列先把K个链表的头节点放进一个大小为K的最小堆每次从堆里弹出最小的节点接到新链表上再把这个节点的next节点推入堆中。因为堆操作是O(logK)的总复杂度是O(total * logK)其中total是所有节点的总数。实现时哑节点的作用依然明显堆的初始化和每次“弹出的节点接上再把后继节点塞回去”这个流程仔细看就是第21题每步操作的泛化版本。6.2 为什么优先队列能保证顺序你可能会想堆里只存K个元素凭什么弹出来的顺序就是全局有序的原因很简单——K个链表各自内部都是升序的所以全局最小值一定出现在K个链表的头节点之一。每弹出一个最小头节点它的后继节点成为自己链表的新头放进堆里参与下一轮比较。堆始终维护着K个链表的当前头每次弹出的都是所有剩余节点里的最小值。这个过程保证了全局升序不需要额外比较其他节点。6.3 其他相关变种题目顺着这个思路还可以接着看第88题“合并两个有序数组”这是链表合并的数组版本要求原地合并第148题“排序链表”要求在O(n log n)时间内对链表排序归并排序的合并步骤就是本题的迭代版。把第21题和这几题放在一起刷你会明显感觉到“合并有序序列”这个主题的普适性。我自己的刷题顺序是第21题 → 第88题 → 第23题 → 第148题每道题都试图在上一题的基础上增加一点点复杂度。这样比在网上随机刷题要高效得多因为每道题的知识点都有重合理解深度会层层递进。7. 最后聊聊刷题的取舍第21题虽然简单但它给了我一个很重要的提醒很多题目的价值不在“会不会做”而在“能不能讲清楚”。我见过不少人看一遍题解就觉得自己会了但面试时要求手写这个函数写是写出来了问一句“为什么这里要用哑节点”就答不上来。如果你现在开始刷链表题我的建议是不要只做这一道就往前冲。把它和上面提到的几道题放在一组用一个周末集中突破。判断标准很简单不看答案能不能写出迭代版和递归版、能不能画出递归调用过程、能不能说清时间和空间复杂度、能不能在追问“如果是K个链表呢”时给出思路。这题还有一个容易被忽略的点在新链表上我们直接复用了原有链表节点没有新建任何节点。这一点在面试中值得主动提一句——说明你意识到合并操作是“改变指针指向”而不是“复制节点值”。这体现的是对链表这种数据结构本质的理解远比背代码更能打动面试官。我记得自己第一次在纸上画这道题的递归展开时画了整整一页才真正明白每一层调用发生了什么。从那以后再碰到链表递归题我都有了章法先判断当前层需要解决的最小问题找到递归体和终止条件其余交给函数自身。第21题恰好是建立这种思维最好的训练场。希望这篇拆解能帮你省下一些当初我绕过的弯路。

合并两个有序链表详解：迭代、递归与复杂度分析

相关推荐

思腾昇腾服务器大模型部署实战：从NPU到MindIE的完整链路

昇腾AI芯片技术路线图深度解析：从达芬奇架构到训练推理落地

FDTD反射率仿真全流程：从材料导入到曲线分析的完整实操指南

更多资讯

工程伦理核心知识点全解析：责任困境、伦理决策与经典案例

CPRI帧结构深度解析：同步字、控制域与实测排障

DPO偏好优化：如何用二分类替代强化学习实现大模型对齐

Cadence安装全指南：Linux系统级适配与故障排查

RK3588 HDMI IN热插拔问题剖析：从HPD到UEvent的完整链路

图书馆管理信息系统数据库设计：从ER建模到SQL事务与索引优化

今日更新

45个经典Linux面试题：从命令到网络排障的完整考点解析

SAP生产预留实战指南：MB21/MB23/MB25协同与MRP集成

编译原理实验：递归下降分析器消除左递归与避坑指南

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？