示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本文基于 doocs/leetcode 开源仓库中 《剑指 Offer第 2 版》面试题 25 的官方题解整理而成。这道题要求将两条递增排序的链表合并成一条仍然递增的新链表是链表类面试题的经典入门题其解法也是归并排序、合并 K 个有序链表等进阶问题的基础。读完本文你将掌握「哑结点 双指针迭代」与「递归」两种解法并能对照 Python、Java、C、Go、TypeScript、Rust、JavaScript、C#、Swift 九种语言的完整实现理解各自的时空复杂度与适用场景。题目理解题目描述输入两个递增排序的链表合并这两个链表并使新链表中的节点仍然是递增排序的。示例 1输入1-2-4, 1-3-4 输出1-1-2-3-4-4限制条件0 链表长度 1000需要特别注意的是本题与主站 LeetCode 21 题合并两个有序链表完全相同仓库在 solution/0000-0099/0021.Merge Two Sorted Lists/README.md 中收录了对应的主站题解可以相互对照学习。核心约束解读两条链表本身已经各自有序因此无需重新排序只需在两条链表的节点间做「归并」式的穿插拼接新链表不能简单地把两个链表首尾相接因为那样会破坏递增序合并过程不能新建大量节点通常要求直接复用原链表节点仅调整指针指向。解法一迭代 哑结点dummy node思路分析这是最直观、最稳妥的解法核心思想可以概括为四句话两链表各自有序合并后仍须有序每次取较小头结点接到结果后即可无需再排序用哑结点统一拼接谁小接谁剩余整段挂到末尾先创建一个虚拟头结点dummy再创建一个指针cur指向dummy循环比较l1和l2当前节点的值把值较小的节点接到cur后面同时将该链表指针向后移动一位循环结束后把cur指向l1或l2中剩余的那一段最后返回dummy.next。哑结点的作用如果不使用dummy那么合并后链表的第一个节点需要单独判断是l1还是l2的头节点代码会出现分支重复。而引入dummy后所有节点包括第一个都被「统一地」接到cur.next上循环逻辑变得干净一致最后只需要返回dummy.next即可拿到真实头节点。这一技巧在链表题中极其常用例如反转链表、两两交换节点等场景都能受益。复杂度时间复杂度 O(m n)空间复杂度 O(1)只用了常数额外指针。其中 m 和 n 分别为两个链表的长度。Python3# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val x # self.next None class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) - ListNode: dummy cur ListNode(0) 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 or l2 return dummy.nextPython 版本中cur.next l1 or l2充分利用了 Python 的短路求值l1非空时接l1否则接l2即使l2也为空接None也完全正确链表以None结尾。Java/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val x; } * } */ 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 ? l2 : l1; return dummy.next; } }C/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* dummy new ListNode(0); ListNode* cur dummy; while (l1 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 ? l1 : l2; return dummy-next; } };注意 C 版通过new ListNode(0)在堆上创建哑结点实际工程中若用智能指针管理节点可避免手动释放的负担在 LeetCode 评测环境中内存由框架统一回收。Go/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { dummy : ListNode{} cur : dummy for l1 ! nil l2 ! nil { if l1.Val l2.Val { cur.Next l1 l1 l1.Next } else { cur.Next l2 l2 l2.Next } cur cur.Next } if l1 nil { cur.Next l2 } else { cur.Next l1 } return dummy.Next }Go 版中dummy : ListNode{}创建零值哑结点Val为 0此值无关紧要因为哑结点不会作为结果的一部分返回。TypeScript/** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val?: number, next?: ListNode | null) { * this.val (valundefined ? 0 : val) * this.next (nextundefined ? null : next) * } * } */ function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null { const dummy new ListNode(0); let cur dummy; while (l1 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 || l2; return dummy.next; }Rust// Definition for singly-linked list. // #[derive(PartialEq, Eq, Clone, Debug)] // pub struct ListNode { // pub val: i32, // pub next: OptionBoxListNode // } // // impl ListNode { // #[inline] // fn new(val: i32) - Self { // ListNode { // next: None, // val // } // } // } impl Solution { pub fn merge_two_lists( mut l1: OptionBoxListNode, mut l2: OptionBoxListNode, ) - OptionBoxListNode { match (l1.is_some(), l2.is_some()) { (false, false) None, (true, false) l1, (false, true) l2, (true, true) { let mut dummy Box::new(ListNode::new(0)); let mut cur mut dummy; while l1.is_some() l2.is_some() { cur.next if l1.as_ref().unwrap().val l2.as_ref().unwrap().val { let mut res l1.take(); l1 res.as_mut().unwrap().next.take(); res } else { let mut res l2.take(); l2 res.as_mut().unwrap().next.take(); res }; cur cur.next.as_mut().unwrap(); } cur.next if l1.is_some() { l1.take() } else { l2.take() }; dummy.next.take() } } } }Rust 版本由于所有权的存在是所有实现中写法最「绕」的一种节点类型是OptionBoxListNode需要通过take()从Option中移出所有权用as_mut()获得可变引用再移动内部指针。这也是 Rust 刷链表题时最具代表性的模式理解了这道题就理解了 Rust 中链表指针操作的大部分惯用法。JavaScript/** * Definition for singly-linked list. * function ListNode(val) { * this.val val; * this.next null; * } */ /** * param {ListNode} l1 * param {ListNode} l2 * return {ListNode} */ var mergeTwoLists function (l1, l2) { const dummy new ListNode(0); let cur dummy; while (l1 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 || l2; return dummy.next; };C#/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { val x; } * } */ public 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 ? l2 : l1; return dummy.next; } }Swift/* public class ListNode { * var val: Int * var next: ListNode? * init(_ val: Int) { * self.val val * self.next nil * } * } */ class Solution { func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) - ListNode? { let dummy ListNode(0) var cur: ListNode? dummy var l1 l1 var l2 l2 while let l1Node l1, let l2Node l2 { if l1Node.val l2Node.val { cur?.next l1Node l1 l1Node.next } else { cur?.next l2Node l2 l2Node.next } cur cur?.next } cur?.next l1 ?? l2 return dummy.next } }边界情况小结迭代法输入情况处理结果l1为空l2非空循环不进入cur.next l2直接返回整段l2l1非空l2为空循环不进入cur.next l1直接返回整段l1两者皆为空cur.next接None返回dummy.next即None两条链表长度不等短链表先耗尽剩余长链表整段挂到末尾天然有序解法二递归思路分析迭代已能线性完成但实现稍长。递归的思路则更简洁递归比较两头较小者的next接到合并后的剩余部分空间随递归深度增长。具体步骤先判断l1和l2中有没有一个为空如果有一个为空那么直接返回另一个链表即可比较l1和l2当前节点的值如果l1的值小于等于l2的值递归调用mergeTwoLists(l1.next, l2)并将返回的链表接到l1.next上然后返回l1如果l1的值大于l2的值递归调用mergeTwoLists(l1, l2.next)并将返回的链表接到l2.next上然后返回l2。之所以可行是因为「合并两个有序链表」这个子问题在每次递归调用中保持同构选定较小的头节点后剩余部分依然是两条有序链表只是其中一条变短了当某一侧为空时另一侧整段即为结果递归自然终止。复杂度时间复杂度 O(m n)空间复杂度 O(m n)递归调用栈的深度。注意递归版的空间复杂度取决于递归深度最坏情况下深度为 m n例如1-2-3-...与2-3-4-...交替取节点因此当链表长度很大时迭代版在空间上更优。Python3# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val x # self.next None class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) - ListNode: if l1 is None or l2 is None: return l1 or l2 if l1.val l2.val: l1.next self.mergeTwoLists(l1.next, l2) return l1 else: l2.next self.mergeTwoLists(l1, l2.next) return l2Java/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val x; } * } */ class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 null) { return l2; } if (l2 null) { return l1; } if (l1.val l2.val) { l1.next mergeTwoLists(l1.next, l2); return l1; } else { l2.next mergeTwoLists(l1, l2.next); return l2; } } }C/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (!l1) { return l2; } if (!l2) { return l1; } if (l1-val l2-val) { l1-next mergeTwoLists(l1-next, l2); return l1; } else { l2-next mergeTwoLists(l1, l2-next); return l2; } } };Go/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { if l1 nil { return l2 } if l2 nil { return l1 } if l1.Val l2.Val { l1.Next mergeTwoLists(l1.Next, l2) return l1 } else { l2.Next mergeTwoLists(l1, l2.Next) return l2 } }TypeScript/** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val?: number, next?: ListNode | null) { * this.val (valundefined ? 0 : val) * this.next (nextundefined ? null : next) * } * } */ function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null { if (l1 null || l2 null) { return l1 || l2; } if (l1.val l2.val) { l1.next mergeTwoLists(l1.next, l2); return l1; } l2.next mergeTwoLists(l1, l2.next); return l2; }Rust// Definition for singly-linked list. // #[derive(PartialEq, Eq, Clone, Debug)] // pub struct ListNode { // pub val: i32, // pub next: OptionBoxListNode // } // // impl ListNode { // #[inline] // fn new(val: i32) - Self { // ListNode { // next: None, // val // } // } // } impl Solution { pub fn merge_two_lists( l1: OptionBoxListNode, l2: OptionBoxListNode, ) - OptionBoxListNode { match (l1, l2) { (Some(mut n1), Some(mut n2)) { if n1.val n2.val { n1.next Self::merge_two_lists(n1.next, Some(n2)); Some(n1) } else { n2.next Self::merge_two_lists(Some(n1), n2.next); Some(n2) } } (Some(node), None) Some(node), (None, Some(node)) Some(node), (None, None) None, } } }JavaScript/** * Definition for singly-linked list. * function ListNode(val) { * this.val val; * this.next null; * } */ /** * param {ListNode} l1 * param {ListNode} l2 * return {ListNode} */ var mergeTwoLists function (l1, l2) { if (!(l1 l2)) { return l1 || l2; } if (l1.val l2.val) { l1.next mergeTwoLists(l1.next, l2); return l1; } else { l2.next mergeTwoLists(l2.next, l1); return l2; } };C#/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { val x; } * } */ public class Solution { public ListNode MergeTwoLists(ListNode l1, ListNode l2) { if (l1 null) { return l2; } if (l2 null) { return l1; } if (l1.val l2.val) { l1.next MergeTwoLists(l1.next, l2); return l1; } else { l2.next MergeTwoLists(l1, l2.next); return l2; } } }两种解法对比与选型维度迭代 哑结点递归时间复杂度O(m n)O(m n)空间复杂度O(1)仅常数个指针O(m n)递归调用栈代码风格过程式、直观无栈溢出风险声明式、更简洁逻辑同构适用场景链表很长、对空间敏感、面试求稳链表较短、强调代码优雅、语言递归优化良好实际面试中两种写法都值得掌握迭代版作为保底方案永远安全递归版可作为亮点展示对递归思维的理解。递归版在 Rust 等对所有权要求严格的语言中写法反而比迭代版更接近直觉不需要手动移动所有权。仓库中的对应实现与验证doocs/leetcode 仓库在 lcof/面试题25. 合并两个排序的链表/ 目录下提供了与本文完全一致的独立可提交源码迭代版Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.js、Solution.rs、Solution.swift、Solution.ts、Solution.cs递归版Solution2.py、Solution2.java、Solution2.cpp、Solution2.go、Solution2.js、Solution2.rs、Solution2.ts、Solution2.cs。同时在 lcof/README.md 的题目索引表中本题被标记为「分治算法 · 简单」与solution/0000-0099/0021.Merge Two Sorted Lists/README.md中主站 21 题的「递归 · 链表」标签相互印证——合并有序链表本质上是分治归并思想的原子操作主站版本LeetCode 21在 solution/0000-0099/0021.Merge Two Sorted Lists/ 目录下其 README 额外给出了三个边界示例l1[]、l2[]、l1[]、l2[0]建议对照阅读以强化对边界情况的理解。实战延伸这道题的价值在哪里「合并两个有序链表」远不止是一道面试题它是若干高频问题的基础积木归并排序链表版链表的归并排序正是「拆分成两半 → 递归排序 → 合并两个有序链表」三步本解法直接构成 merge 步骤合并 K 个有序链表主站 23 题可通过两两合并本解法或优先队列求解本解法是其中最朴素的一版多路归并思想外排序、数据库归并段合并等场景底层都是把多个有序序列两两或 K 路归并成一个有序序列本题正是最小规模的单元。建议动手方式先独立写出迭代版并通过示例用例含1-2-4与1-3-4这类含重复值的用例注意比较时使用以保证稳定性验证再写出递归版并对比两种写法在「两条链表长度悬殊」时的行为差异。将两版代码分别与仓库目录下的Solution.*/Solution2.*源码核对即可确认实现与官方题解完全一致。赞分享示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐CS-Notes 剑指 Offer 题解 25合并两个排序的链表 —— 递归、迭代两种写法与复杂度对比CS Notes 剑指 Offer 题解 25合并两个排序的链表 —— 递归、迭代两种写法与复杂度对比 本篇基于 CS Notes 剑指 Offer 题解中的知识库文档教程LogicStack-LeetCode 详解剑指 Offer 25合并两个排序链表的迭代哨兵法与递归解法LogicStack LeetCode 详解剑指 Offer 25合并两个排序链表的迭代哨兵法与递归解法 本文基于「刷穿 LeetCode」系列仓库 Logi教程文档剑指 Offer No16 合并两个有序链表四种迭代与递归写法全解析剑指 Offer No16 合并两个有序链表四种迭代与递归写法全解析 本篇技术指南以 InterviewGuide 仓库《带你快速刷完67道剑指offer》系文档教程知识库上一篇HexFiend框架集成终极指南如何在你的App中快速嵌入专业十六进制视图下一篇FastAPI 调试实战用 uvicorn.run 直接启动让 VS Code 与 PyCharm 断点生效创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
