CS-Notes 剑指 Offer 题解 25合并两个排序的链表 —— 递归、迭代两种写法与复杂度对比【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes本篇基于 CS-Notes 剑指 Offer 题解中的第 25 题「合并两个排序的链表」展开完整讲解如何将两个升序单链表原地合并为一个新的升序链表先给出递归与迭代两套完整可运行的 Java 实现再逐行拆解 dummy 节点技巧与递归终止条件最后对比两种写法的空间开销与栈溢出风险并结合归并排序中的 merge 步骤说明该思想的延伸应用。读完本文你可以独立在面试白板上一口气写出两种实现并准确回答时间/空间复杂度提问。题目描述输入两个递增排序的链表合并这两个链表并使新链表中的节点仍然是按照递增排序返回合并后的链表头。这是单链表操作的基础题也是归并排序Merge Sort中 merge 阶段的链表版本在剑指 Offer 题解中被归入链表分类可在 剑指 Offer 题解 - 目录 的「链表」一节中找到本题的入口。解法一递归原文档给出的递归实现如下引自 notes/25. 合并两个排序的链表.mdpublic ListNode Merge(ListNode list1, ListNode list2) { if (list1 null) return list2; if (list2 null) return list1; if (list1.val list2.val) { list1.next Merge(list1.next, list2); return list1; } else { list2.next Merge(list1, list2.next); return list2; } }逐行拆解这段代码的设计要点两个递归终止条件list1 null时直接返回list2list2 null时直接返回list1。因为剩余部分本身就是有序链表直接拼接即可无需逐个节点处理。每层只做一个比较、一次链接比较两个头节点val后较小者作为当前段的头并把它的next指向「剩余部分递归合并的结果」。由于是原地修改next指针不新建任何节点因此结果链表复用了输入链表的节点。比较使用当list1.val list2.val时优先取list1的节点这个选择保证了合并结果对相同值的处理是确定的稳定地偏向 list1面试时可以主动提一句这一点。复杂度每一层递归恰好消耗两个链表中的一个节点总比较次数为m nm、n 为两表长度时间复杂度 O(m n)递归深度最坏达到 m n每层调用占用 O(1) 栈帧空间复杂度 O(m n)。解法二迭代dummy 节点技巧原文档同时给出了迭代版本public ListNode Merge(ListNode list1, ListNode list2) { ListNode head new ListNode(-1); ListNode cur head; while (list1 ! null list2 ! null) { if (list1.val list2.val) { cur.next list1; list1 list1.next; } else { cur.next list2; list2 list2.next; } cur cur.next; } if (list1 ! null) cur.next list1; if (list2 ! null) cur.next list2; return head.next; }这段实现的关键点dummy哨兵节点head是一个值为 -1 的占位节点cur始终指向结果链表的尾指针。使用 dummy 节点的好处是统一了头节点初始化和后续插入两种操作——循环里只需要写cur.next ...一种形式最后返回head.next跳过哨兵即可。这和 24. 反转链表 等链表题中常见的 dummy 手法一致是链表题的通用技巧。while 循环的条件是list1 ! null list2 ! null只要两条链表都还有节点就每轮比较并接上较小的一个同时推进对应链表的指针和cur。循环结束后至多有一个链表还有剩余也可能都已耗尽。尾部拼接循环外的两个if把剩余部分整体接到cur.next。因为剩余链表自身有序直接接上即可无需再遍历。两个if实际上互斥不可能同时非空写成两个独立 if 是为了代码简洁。复杂度时间 O(m n)每个输入节点恰好被访问一次空间上除了返回结果外只用了 O(1) 的指针变量。与递归版相比它没有调用栈开销链表很长时不会出现栈溢出是更稳妥的面试写法。递归 vs 迭代对比维度递归版迭代版时间复杂度O(m n)O(m n)额外空间O(m n)递归栈深度最坏 m nO(1)风险链表过长时栈溢出无代码长度更短逻辑集中稍长需处理 dummy 与尾部拼接推荐场景展示分治思维、数据规模可控生产环境、数据规模未知两套代码在本题的约束下都是原地合并复用原节点、只改next指针没有额外申请结果节点这一点在面试中容易被追问值得主动说明。该思想在仓库其他题解中的延伸「比较两个有序序列的头、接较小者」是归并思想的核心动作在本仓库中至少还有两处同源应用归并排序的 merge 步骤51. 数组中的逆序对 用归并排序统计逆序对其中的merge(nums, l, m, h)函数就是数组版的合并逻辑——从左右两半分别取较小的元素写入临时数组tmp该文件还特意在类级别声明tmp辅助数组而非在 merge 递归函数中声明以减少递归过程中的重复分配这是一个值得学习的工程细节。Leetcode 21. Merge Two Sorted ListsLeetcode 题解 - 链表 中「3. 归并两个有序的链表」一节给出的mergeTwoLists递归实现与剑指 25 的递归版结构完全一致比较两头、小者接后续递归结果只是判等时优先取l1l1.val l2.val分支可以对照阅读验证同一套写法在不同题目模板下的形态。此外本题也是「合并 K 个排序链表」可用小根堆或分治两两合并的基础组件而 23. 链表中环的入口结点 等链表题则提醒我们在写链表代码前先想清楚边界空表、单节点本题中两个链表同时为空的输入在两种实现下都能正确返回 null递归版命中第一个终止条件迭代版直接返回head.next即 null。小结递归写法用两个终止条件 一层「比较并链接」即可完成合并代码最短但空间开销为 O(m n) 的递归栈迭代写法用 dummy 节点统一插入逻辑循环结束后整体拼接剩余部分空间 O(1)是面试中最推荐的白板实现两种写法时间复杂度均为 O(m n)且都是原地修改指针、复用原节点的合并掌握本题后可以顺势理解归并排序的 merge 阶段以及 K 路归并的分治构造这也是本仓库 剑指 Offer 题解 - 目录 中「链表」与「排序」两个分类之间的天然衔接点。【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考