力扣热题100实战 | 第21期合并两个有序链表——链表操作的入门必修课前言一、题目把两条有序链表串成一条关键点解读二、核心解法一迭代法 虚拟头节点面试首选为什么需要虚拟头节点算法步骤图解流程代码实现代码解析复杂度分析三、核心解法二递归法简洁优雅递归思想图解递归过程代码实现代码解析复杂度分析四、迭代法 vs 递归法巅峰对决面试建议五、细节剖析面试官真正关心的问题Q1为什么用虚拟头节点而不用直接判断头节点Q2迭代法中为什么最后处理剩余节点时可以直接 prev.next (list1 null) ? list2 : list1Q3递归解法中为什么能直接修改原链表的 next 指针Q4两种解法的时间复杂度都是 O(nm)实际运行哪个更快Q5如果链表是降序的代码需要怎么改六、面试官追问进阶版追问1如何合并 K 个有序链表LeetCode 23追问2如果要求合并后**去重**不能有重复值怎么改追问3如何用迭代法实现但不用虚拟头节点七、实际开发这道题到底有什么用场景1归并排序中的合并阶段场景2数据库查询的合并操作场景3多路归并外部排序场景4合并多个有序日志文件场景5有序流的合并八、总结从一道题到一类题附录思考题如果说数组的“Hello World”是两数之和那链表的“Hello World”非合并两个有序链表莫属。这道题虽简单却是理解链表指针操作的基石更是通往复杂链表问题的必经之路。前言你好我是礼拜天没时间。上一期我们学习了有效的括号掌握了栈结构的经典应用。这一期我们回到链表专题来解一道链表操作的入门必修课——合并两个有序链表LeetCode 第21题。这道题在力扣上被标记为“简单”但它的简单并不意味着可以轻视。恰恰相反这道题是理解链表指针操作的基石。很多初学者第一次接触链表时总是被“指针移动”“节点连接”绕晕。而这道题正是帮你理清这些概念的最佳练习场。更重要的是这道题有两种经典的解法——迭代和递归。掌握这两种思路不仅能解决这道题还能为你后续学习更复杂的链表问题如合并K个有序链表打下坚实的基础。今天我希望能带你从两种角度审视这道题彻底掌握链表合并的核心技巧。一、题目把两条有序链表串成一条先看题目描述LeetCode 第21题将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例 1输入l1 [1,2,4], l2 [1,3,4] 输出[1,1,2,3,4,4]示例 2输入l1 [], l2 [] 输出[]示例 3输入l1 [], l2 [0] 输出[0]提示两个链表的节点数目范围是[0, 50]-100 Node.val 100l1和l2均按非递减顺序排列关键点解读“拼接”的含义题目要求通过拼接给定的两个链表的节点来组成新链表这意味着我们不能简单地创建新节点并复制值而是要直接调整原有节点的指向关系。这是链表操作的核心思想。升序性质两个输入链表本身都是升序的这为我们提供了很大的便利——我们只需要不断比较两个链表的当前节点取较小的那个即可。空链表处理当其中一个链表为空时直接返回另一个链表即可。这是边界情况也是递归解法中重要的终止条件。二、核心解法一迭代法 虚拟头节点面试首选为什么需要虚拟头节点在链表操作中我们经常需要处理“头节点”的特殊情况——如果新链表还没有任何节点那么第一个节点需要被特殊对待。虚拟头节点dummy node就是为了解决这个问题而生的。虚拟头节点的作用避免单独处理“新链表头节点”的边界问题统一新链表的构建逻辑——所有节点都通过prev.next接入无需单独判断第一个节点虚拟头节点是一个真实存在的节点只是它的值没有意义我们最终返回的是dummy.next算法步骤创建虚拟头节点dummy和一个游标指针prev指向它双指针遍历两个链表比较当前节点的值取较小值的节点接入新链表对应链表的指针后移游标指针prev后移处理剩余节点当其中一个链表遍历完后将另一个链表的剩余部分直接接在新链表末尾返回结果返回dummy.next跳过虚拟头节点图解流程以l1 [1,2,4],l2 [1,3,4]为例初始状态dummy - null prev指向dummy l1: 1 - 2 - 4 l2: 1 - 3 - 4第1步比较 l1.val1 和 l2.val1取 l1相等时优先取哪个都行dummy - 1 - ... prev指向节点1 l1移动到2第2步比较 l1.val2 和 l2.val1取 l2dummy - 1 - 1 - ... prev指向节点1第二个 l2移动到3第3步比较 l1.val2 和 l2.val3取 l1dummy - 1 - 1 - 2 - ... prev指向节点2 l1移动到4第4步比较 l1.val4 和 l2.val3取 l2dummy - 1 - 1 - 2 - 3 - ... prev指向节点3 l2移动到4第5步比较 l1.val4 和 l2.val4取 l1dummy - 1 - 1 - 2 - 3 - 4 - ... prev指向节点4第一个 l1移动到null第6步l1 已空将 l2 剩余部分4直接接上最终结果1 - 1 - 2 - 3 - 4 - 4代码实现/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */classSolution{publicListNodemergeTwoLists(ListNodelist1,ListNodelist2){// 1. 创建虚拟头节点ListNodedummynewListNode(-1);// 2. 游标指针用于构建新链表ListNodeprevdummy;// 3. 双指针遍历当两个链表都非空时比较while(list1!nulllist2!null){if(list1.vallist2.val){prev.nextlist1;// 接入list1的当前节点list1list1.next;// list1指针后移}else{prev.nextlist2;// 接入list2的当前节点list2list2.next;// list2指针后移}prevprev.next;// 游标指针后移}// 4. 处理剩余节点最多一个链表有剩余// 利用三元运算符一行代码搞定prev.next(list1null)?list2:list1;// 5. 返回虚拟头节点的下一个节点真正的头节点returndummy.next;}}代码解析虚拟头节点dummy值设为 -1任意值都可以它的存在让我们不需要单独判断新链表的第一个节点从哪里来。游标指针prev始终指向新链表的最后一个节点用于接入下一个节点。循环条件while (list1 ! null list2 ! null)只处理两个链表都有节点的情况。当其中一个遍历完时退出循环。比较逻辑list1.val list2.val取较小值的节点。相等时优先取 list1 不影响结果。剩余节点处理prev.next (list1 null) ? list2 : list1这是链表操作中的经典写法。由于输入链表是升序的剩余部分的所有值都大于已合并部分直接接入不会破坏升序性质。返回值dummy.next跳过虚拟头节点返回真正的头节点。复杂度分析时间复杂度O(n m) —— 需要遍历两个链表的所有节点n 和 m 分别是两个链表的长度空间复杂度O(1) —— 只用了虚拟头节点和游标指针无额外空间三、核心解法二递归法简洁优雅递归思想递归解法体现了“分而治之”的思想递推公式比较两个链表的头节点取较小的那个节点它的next指向“剩下部分合并后的结果”终止条件当其中一个链表为空时直接返回另一个链表用数学语言表达merge(l1, l2) - 如果 l1 null返回 l2 - 如果 l2 null返回 l1 - 如果 l1.val l2.val则 l1.next merge(l1.next, l2); 返回 l1 - 否则l2.next merge(l1, l2.next); 返回 l2图解递归过程以l1 [1,2,4],l2 [1,3,4]为例递归调用栈从顶向下merge(1→2→4, 1→3→4) 比较 1 和 1相等走 else 分支 → merge(1→2→4, 3→4) // 取 l2 的 1 比较 1 和 3 → merge(2→4, 3→4) // 取 l1 的 1 比较 2 和 3 → merge(4, 3→4) // 取 l1 的 2 比较 4 和 3 → merge(4, 4) // 取 l2 的 3 比较 4 和 4 → merge(null, 4) // 取 l1 的 4 return 4 // l1 空返回 l2 的 4 ← 返回 4→4 ← 返回 3→4→4 ← 返回 2→3→4→4 ← 返回 1→2→3→4→4 ← 返回 1→1→2→3→4→4代码实现classSolution{publicListNodemergeTwoLists(ListNodelist1,ListNodelist2){// 终止条件如果其中一个链表为空直接返回另一个if(list1null){returnlist2;}if(list2null){returnlist1;}// 比较当前节点值选择较小的if(list1.vallist2.val){// list1 的当前节点较小它的下一个节点由剩余部分合并得到list1.nextmergeTwoLists(list1.next,list2);returnlist1;}else{// list2 的当前节点较小或相等list2.nextmergeTwoLists(list1,list2.next);returnlist2;}}}代码解析终止条件递归必须要有出口。这里当任一链表为空时返回另一个链表。递归选择比较当前两个头节点的值取较小的那个作为合并后链表的头节点。递归调用被选中的节点它的next应该指向“剩余部分合并的结果”。这里直接调用自身传入剩余部分。返回值返回当前选中的节点它将成为上一层递归的next。复杂度分析时间复杂度O(n m) —— 每个节点都会被递归调用一次空间复杂度O(n m) —— 递归调用栈的深度最坏情况下需要递归 nm 层四、迭代法 vs 递归法巅峰对决维度迭代法递归法代码简洁度中等逻辑清晰极简5行核心代码空间复杂度O(1)O(nm)递归栈风险无链表过长时可能栈溢出可读性容易理解指针移动需要理解递归思维工程实践✅ 推荐生产级写法⚠️ 谨慎使用栈溢出风险面试建议优先掌握迭代法原因有三空间效率高无栈溢出风险逻辑直观指针移动的过程容易向面试官解释虚拟头节点的技巧在后续链表题中会反复用到递归法作为加分项在写完迭代法后可以补充说“这道题也可以用递归实现代码更简洁但需要注意递归深度”展示你的思维广度。五、细节剖析面试官真正关心的问题Q1为什么用虚拟头节点而不用直接判断头节点答案如果不使用虚拟头节点代码需要单独处理新链表的第一个节点// 没有 dummy 的写法ListNodeheadnull;ListNodetailnull;if(list1.vallist2.val){headlist1;taillist1;list1list1.next;}else{// 类似处理}// 然后才开始循环处理剩余节点这样代码冗长且容易出错。虚拟头节点让所有节点的处理逻辑统一是链表操作中的经典技巧。Q2迭代法中为什么最后处理剩余节点时可以直接prev.next (list1 null) ? list2 : list1答案这依赖于输入链表是升序的前提。当其中一个链表遍历完时另一个链表剩余的节点都大于已合并部分的最后一个节点因为原链表升序剩余部分内部也是升序的所以直接接入不会破坏整个链表的升序性质。Q3递归解法中为什么能直接修改原链表的next指针答案因为题目要求“拼接”节点而不是复制节点。我们直接操作原链表的引用关系让它们的next指向新的后继。这是链表操作的核心思想——通过改变指针来重组链表而不是创建新对象。Q4两种解法的时间复杂度都是 O(nm)实际运行哪个更快答案迭代法通常更快因为递归有函数调用开销。但在本题数据规模较小节点数 ≤ 50的情况下差异可以忽略不计。Q5如果链表是降序的代码需要怎么改答案核心逻辑完全不变——仍然是比较两个头节点取较大的那个。只需要把比较符号从改成即可。因为“有序”的性质本身才是关键升序还是降序只是比较规则不同。六、面试官追问进阶版追问1如何合并 K 个有序链表LeetCode 23思路这是本题的进阶版有多种解法逐一合并用第21题的方法两两合并时间复杂度 O(k²n)分治合并类似归并排序两两分组合并时间复杂度 O(kn log k)优先队列用最小堆维护 K 个头节点每次取最小的时间复杂度 O(kn log k)// 分治合并的框架publicListNodemergeKLists(ListNode[]lists){if(lists.length0)returnnull;returnmerge(lists,0,lists.length-1);}privateListNodemerge(ListNode[]lists,intleft,intright){if(leftright)returnlists[left];intmidleft(right-left)/2;ListNodel1merge(lists,left,mid);ListNodel2merge(lists,mid1,right);returnmergeTwoLists(l1,l2);// 调用第21题的方法}追问2如果要求合并后去重不能有重复值怎么改思路在比较时如果两个节点值相等只接入其中一个然后同时移动两个链表的指针。while(list1!nulllist2!null){if(list1.vallist2.val){prev.nextlist1;list1list1.next;}elseif(list1.vallist2.val){prev.nextlist2;list2list2.next;}else{// 相等时只接入一个两个指针都移动prev.nextlist1;list1list1.next;list2list2.next;}prevprev.next;}追问3如何用迭代法实现但不用虚拟头节点思路先处理头节点再用循环处理后续节点。publicListNodemergeTwoLists(ListNodel1,ListNodel2){if(l1null)returnl2;if(l2null)returnl1;// 先确定头节点ListNodehead;if(l1.vall2.val){headl1;l1l1.next;}else{headl2;l2l2.next;}// 用 tail 指向当前最后一个节点ListNodetailhead;// 循环处理剩余节点while(l1!nulll2!null){if(l1.vall2.val){tail.nextl1;l1l1.next;}else{tail.nextl2;l2l2.next;}tailtail.next;}tail.next(l1null)?l2:l1;returnhead;}这种写法也能工作但代码不如有虚拟头节点时简洁。七、实际开发这道题到底有什么用很多读者会问“合并两个有序链表实际工作中哪用得到”其实它的思想无处不在场景1归并排序中的合并阶段归并排序的核心操作就是合并两个有序数组/链表。掌握这道题你就理解了归并排序的“合”这一步。场景2数据库查询的合并操作在数据库中多个索引查询的结果需要合并时用的就是类似的思想。场景3多路归并外部排序当数据量太大无法全部加载到内存时需要用到多路归并排序。而“合并两个有序链表”就是多路归并的最基础单元。场景4合并多个有序日志文件在日志分析系统中多个服务器产生的有序日志需要合并成全局有序的日志流用的也是这种思想。场景5有序流的合并在数据流处理中多个有序数据流需要合并成一个有序流输出这正是一道“合并K个有序链表”的变体。八、总结从一道题到一类题回顾一下我们从合并两个有序链表学到了什么维度收获算法思维迭代 vs 递归理解两种思路的适用场景代码技巧虚拟头节点的妙用、剩余节点的一行处理、递归的终止条件复杂度分析迭代 O(1) 空间递归 O(nm) 空间递归栈面试要点为什么用虚拟头节点剩余节点为什么可以直接接递归怎么思考工程关联归并排序、数据库合并、多路归并、日志合并力扣热题100的第二十一题不是为了难住你而是为了告诉你链表操作的核心不是创建新节点而是改变指针指向。当你真正理解了这一点你就掌握了链表题的精髓。下一期预告《括号生成》——回溯算法的经典应用附录思考题看完这篇文章你可以试着回答如果要求合并后降序排列代码需要怎么改如何用迭代法合并 K 个有序链表时间复杂度是多少你能用这道题的思路去解 LeetCode 23合并K个升序链表吗欢迎在评论区留下你的思考