合并两个排序链表：哨兵头节点与双指针归并 —— 剑指 Offer 25 在 LeetCode-Book 中的三语言实现解析

合并两个排序链表哨兵头节点与双指针归并 —— 剑指 Offer 25 在 LeetCode-Book 中的三语言实现解析【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本篇基于 LeetCode-Book 仓库中《剑指 Offer》章节的文档 剑指 Offer 25. 合并两个排序的链表完整讲解“双指针 哨兵头节点”的链表归并算法哨兵节点如何消除首节点特殊处理、循环合并与尾部收尾的每一步指针变化以及 Python / Java / C 三套可运行代码的实现差异与复杂度推导并逐行拆解仓库中的参考实现帮助你写出稳定、原地、O(1) 空间的链表合并代码。一、问题描述与解题思路题目要求输入两个递增排序的链表将它们合并到一个新的链表中并返回。例如输入1-2-4与1-3-4应得到1-1-2-3-4-4即 LeetCode 21 题 “Merge Two Sorted Lists” 的经典模型。由于两个链表本身已经有序合并过程天然适合使用双指针分别用指针l1、l2遍历两条链表每次比较l1.val与l2.val的大小把较小的节点接合并到结果链表尾部被选中一侧的指针前进一格两侧指针交替前进直至某条链表遍历完毕循环结束后只需把尚未遍历完的剩余部分整段接到结果尾部即可剩余部分本身依然有序无需再比较。这里有一个实现上的关键难点初始状态下合并链表是空的。如果直接维护head指针第一轮循环就无法确定“第一个节点往哪接”需要对首节点写单独的 if 分支后续每轮还要区分“是否已有前驱节点”代码容易出错。文档给出的标准解法是引入哨兵伪头节点dum先创建一个值为 0 的辅助节点作为合并链表的伪头节点所有待合并节点都挂在dum之后。这样循环体内永远存在一个确定的“接入点”当前节点cur的next无需特判首节点合并完成后真实头节点就是dum.next直接返回即可。哨兵节点是链表题的通用技巧——本仓库的 Python 工具函数 list_to_linked_list 在“数组转链表”时也采用了完全相同的模式dum head ListNode(0)循环结束后返回dum.next可见该技巧在仓库内是被刻意统一使用的。二、算法流程四步走依据原文档的算法流程完整过程分为四步初始化创建哨兵节点dum ListNode(0)并让移动指针cur指向dum。此后cur始终指向“结果链表的最后一个节点”cur.next就是下一个空位。循环合并当l1和l2都非空时继续循环任一条链表为空while条件不满足时跳出。每轮迭代若l1.val l2.val将cur.next指定为l1然后l1向前走一步若l1.val l2.val将cur.next指定为l2然后l2向前走一步最后cur也向前走一步即cur cur.next指向刚接入的那个节点新的结果尾部。合并剩余尾部跳出循环时l1与l2中必有一条为空另一条至多为空。把非空的整条余链接到cur.next若l1非空则接l1否则接l2。由于余链本身有序整段接管不会破坏整体有序性。返回值合并结果挂在哨兵节点之后因此返回dum.next。几个值得注意的细节原地合并、零新节点整个过程不新建任何数据节点只是重新指向原链表节点因此输入链表的节点归属会被改写短链表尾部的next将被重定向这是允许的因为题目只要求返回合并后的链表稳定性比较条件是严格小于l1.val l2.val当两节点值相等时走else分支、优先取l2的节点。这一细节保证了相等元素按“先遇到的在前”的顺序入链使合并操作具备归并排序的稳定性在后续扩展为 k 路归并时尤为重要哨兵值不参与比较dum的值0只是占位循环体内比较的始终是l1与l2的当前节点哨兵本身永远不会被比较或被错误并入结果。三、三语言参考实现含逐行注释仓库sword_for_offer/codes目录下为本题提供了三套独立可运行的实现均带测试用例[1, 2, 4]合并[1, 3, 4]。以下给出带注释的完整代码。Python 实现参考 sfo_25_combine_two_sorted_linked_lists_s1.pyclass Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) - ListNode: # 哨兵节点 dum 与移动指针 cur 同时指向 dum结果链表初始为空cur.next 是第一个空位 cur dum ListNode(0) # 双指针归并两条链表都还有节点时循环 while l1 and l2: if l1.val l2.val: # Python 元组解包一步完成两件事cur.next 指向 l1同时 l1 前进一格 cur.next, l1 l1, l1.next else: cur.next, l2 l2, l2.next cur cur.next # cur 前进指向刚接入的节点 # 收尾把未走完的那条余链整体接到尾部二者必有一个为 None三目表达式兜底 cur.next l1 if l1 else l2 # 真实头节点在哨兵之后 return dum.nextPython 版最大的特点是元组同时赋值cur.next, l1 l1, l1.next在一条语句内完成“接入 指针前进”。注意右侧先求值先取l1.next的旧值左侧再赋值因此不会像顺序执行两行赋值那样丢失l1.next的引用。文档中专门提示了 Python 三元表达式A if x else B的语义x为真时取A收尾行l1 if l1 else l2正是其应用。文件末尾自带测试驱动第 2530 行l1 list_to_linked_list([1, 2, 4]) l2 list_to_linked_list([1, 3, 4]) slt Solution() res slt.mergeTwoLists(l1, l2) print_linked_list(res) # 输出 1-1-2-3-4-4-Java 实现参考 sfo_25_combine_two_sorted_linked_lists_s1.javaclass Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dum new ListNode(0), cur dum; 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 dum.next; } }Java 版的循环体必须拆成两行完成“接入 前进”没有元组赋值逻辑与 Python 版完全等价。注意参数l1、l2在这里被直接重赋值——方法内修改局部形参并不会影响调用方持有的引用这正体现了“原地改指针、不改节点”的原地合并语义。C 实现参考 sfo_25_combine_two_sorted_linked_lists_s1.cppclass Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* dum new ListNode(0); // 哨兵节点堆上分配 ListNode* cur dum; 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 dum-next; } };C 版与 Java 版的差异在于使用-访问成员、nullptr判空以及哨兵节点通过new在堆上分配。节点类型定义见 ListNode.hppstruct ListNode { int val; ListNode *next; ... }与 Java/Python 中的ListNode字段一一对应。三语言代码在算法层几乎逐行同构方便横向对照阅读。四、示例推演指针如何一步步移动以测试用例l1: 1-2-4、l2: 1-3-4推演整个归并过程dum.val 0cur初始指向dum轮次比较动作合并链dum 之后l1 指向l2 指向11 vs 1l1.val l2.val不成立接l2值 1l2前进11321 3 成立接l1值 1l1前进1-12332 3 成立接l1值 2l1前进1-1-24344 vs 3 不成立接l2值 3l2前进1-1-2-34454 vs 4 不成立接l2值 4l2前进1-1-2-3-44null此时l2 nullwhile条件不满足跳出循环。收尾行cur.next l1 if l1 else l2将剩余的l1值为 4 的节点整段接入得到1-1-2-3-4-4返回dum.next。三套代码的测试驱动均使用这一用例运行后可在控制台看到1-1-2-3-4-4-的打印结果。五、复杂度分析时间复杂度 O(M N)设l1、l2的长度分别为M、N。每次循环恰好消费两个链表中的一个节点循环最多执行M N次收尾的整段接管是 O(1)只改一次指针不遍历余链。总体上每个节点最多被访问一次。空间复杂度 O(1)仅使用dum、cur等常数个节点引用作为额外空间未申请任何数据节点哨兵节点严格来说是 1 个额外节点仍属 O(1)迭代写法还避免了递归方案 O(MN) 的调用栈开销。从源码结构看三套实现Python / Java / C的循环体均无额外容器分配复杂度与文档结论一致且 C 版未释放哨兵节点属于教学代码的常见取舍——若用于生产环境可自行决定是否delete dum。六、在仓库中运行参考代码仓库代码遵循“一个题目一个自包含文件”的组织方式Solution类下方附带测试用例与驱动代码可以直接运行验证Python直接运行 sfo_25_combine_two_sorted_linked_lists_s1.py依赖同目录include/包中的ListNode、list_to_linked_list、print_linked_list工具见 include/init.pyJava编译时需让include/包对编译器可见文件顶部import include.*;入口为main方法C通过#include ../include/include.hpp引入节点定义与打印工具g -stdc17 sfo_25_combine_two_sorted_linked_lists_s1.cpp编译即可。阅读时建议对照 ListNode.hpp 中的vectorToLinkedList它同样先用哨兵节点dum逐格挂接、最后返回dum-next——与本題的“伪头节点”技巧一脉相承可作为理解哨兵模式的第二份素材。七、小结与延伸本文对应 剑指 Offer 刷题计划 中链表章节的 Offer 25 题核心结论可归纳为双指针归并是有序链表合并的最优解法每次比较取小者剩余余链整段接管哨兵头节点是消除首节点特判的标准手法本仓库从题目代码到测试工具函数都统一采用该模式值得作为链表题的默认起手式实现为原地、稳定、O(1) 空间不分配数据节点仅重定向next指针相等值走l2分支这一细节保证了合并的稳定性。在此基础上可以自然延伸把两路归并推广为“合并 K 个升序链表”借助最小堆与归并排序的归并阶段同构本仓库中 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 的 partition 思想、剑指 Offer 51. 数组中的逆序对 的归并排序实现也都建立在“有序序列归并”这一基础能力之上可与本文结合练习。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考