CS-Notes 剑指 Offer 题解 25：合并两个排序的链表 —— 递归、迭代两种写法与复杂度对比

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. 合并两个排序的链表.md）：

public 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时直接返回list2，list2 == null时直接返回list1。因为剩余部分本身就是有序链表，直接拼接即可，无需逐个节点处理。
• 每层只做一个比较、一次链接：比较两个头节点val后，较小者作为当前段的头，并把它的next指向「剩余部分递归合并的结果」。由于是原地修改next指针，不新建任何节点，因此结果链表复用了输入链表的节点。
• 比较使用<=：当list1.val == list2.val时优先取list1的节点，这个选择保证了合并结果对相同值的处理是确定的（稳定地偏向 list1），面试时可以主动提一句这一点。
• 复杂度：每一层递归恰好消耗两个链表中的一个节点，总比较次数为m + n（m、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 迭代对比

两套代码在本题的约束下都是原地合并（复用原节点、只改next指针），没有额外申请结果节点，这一点在面试中容易被追问，值得主动说明。

该思想在仓库其他题解中的延伸

「比较两个有序序列的头、接较小者」是归并思想的核心动作，在本仓库中至少还有两处同源应用：

• 归并排序的 merge 步骤：51. 数组中的逆序对 用归并排序统计逆序对，其中的merge(nums, l, m, h)函数就是数组版的合并逻辑——从左右两半分别取较小的元素写入临时数组tmp；该文件还特意在类级别声明tmp辅助数组（而非在 merge 递归函数中声明），以减少递归过程中的重复分配，这是一个值得学习的工程细节。
• Leetcode 21. Merge Two Sorted Lists：Leetcode 题解 - 链表 中「3. 归并两个有序的链表」一节给出的mergeTwoLists递归实现与剑指 25 的递归版结构完全一致（比较两头、小者接后续递归结果），只是判等时优先取l1（l1.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