文档教程知识库【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址https://gitcode.com/gh_mirrors/le/leetcode点击查看免费下载本篇文章基于 leetcode 题解仓库中的 21.merge-two-sorted-lists.en.md 展开深入讲解合并两个升序链表的经典题LeetCode 第 21 题从问题建模、递归与迭代两种解法到复杂度分析并结合仓库中的链表专题与进阶题目 23. 合并 K 个排序链表帮助读者彻底掌握链表拼接这一类高频考点。题目描述将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例输入1-2-4, 1-3-4 输出1-1-2-3-4-4本题是 LeetCode 上典型的简单难度链表题但它几乎是所有归并类题目如归并排序、合并 K 个有序链表的最小原子操作值得把两种主流解法都吃透。前置知识解决本题之前建议先掌握两个核心概念递归链表天然具有递归结构用递归思想处理每次只比较两个头节点的问题非常直观链表数据结构理解节点valnext指针的组织方式、遍历与指针修改的基本操作。仓库中的 链表专题 thinkings/linked-list.md 系统总结了链表题的两个核心考点——指针的修改与链表的拼接并给出了一个原则画图、两个考点、三个注意、四个技巧的方法论。合并两个有序链表正是链表拼接考点最直接的代表题。解题思路本题可以使用递归来解将两个链表头部较小的一个与剩下的元素合并并返回排好序的链表头当两条链表中的一条为空时终止递归。把递归过程拆解来看若l1为空则直接返回l2剩下的元素全部来自l2若l2为空则直接返回l1否则比较两个头节点的值若l1.val l2.val则l1.next应该指向l1.next与l2合并后的结果返回l1否则l2.next应该指向l1与l2.next合并后的结果返回l2。也就是说递归函数每次只解决当前这一步谁当新链表的头剩余部分交给相同逻辑的递归调用去完成。由于两链表本身有序每次取出较小者就能保证最终结果是全局有序的。关键点掌握链表数据结构熟悉ListNode的定义val与next以及通过next指针遍历、拼接节点的基本操作考虑边界情况两条链表中有一条为空时包含一开始就为空、合并过程中提前耗尽两种情况递归直接返回另一条链表的剩余部分即可。代码实现递归解法仓库中的 21.merge-two-sorted-lists.en.md 提供了 CPP 与 JS 两种语言的递归实现中文版 21.merge-two-sorted-lists.md 还补充了 Java 与 Python 版本一并整理如下。CPP Codeclass Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (l1 nullptr) { return l2; } else if (l2 nullptr) { return l1; } else if (l1-val l2-val) { l1-next mergeTwoLists(l1-next, l2); return l1; } else { l2-next mergeTwoLists(l1, l2-next); return l2; } } };JS Code/** * Definition for singly-linked list. * function ListNode(val) { * this.val val; * this.next null; * } */ /** * param {ListNode} l1 * param {ListNode} l2 * return {ListNode} */ const mergeTwoLists function (l1, 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; } };Java Codeclass Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 null) { return l2; } else if (l2 null) { return l1; } else if (l1.val l2.val) { l1.next mergeTwoLists(l1.next, l2); return l1; } else { l2.next mergeTwoLists(l1, l2.next); return l2; } } }Python Codeclass Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) - ListNode: if not l1: return l2 # 终止条件直到两个链表都空 if not l2: return l1 if l1.val l2.val: # 递归调用 l1.next self.mergeTwoLists(l1.next, l2) return l1 else: l2.next self.mergeTwoLists(l1, l2.next) return l2复杂度分析设两条链表l1、l2的长度分别为M、N时间复杂度$O(MN)$。每次递归调用只处理一个节点合并过程中每个节点最多被访问一次空间复杂度$O(MN)$。递归深度取决于合并链表的长度最坏情况下需要消耗与节点总数等量的函数调用栈空间。需要说明的是递归解法在空间上并不占优。若对栈深度敏感例如链表很长、递归过深可能栈溢出应当改用下面介绍的迭代解法将空间复杂度降为 $O(1)$。扩展迭代解法递归写起来直观但迭代同样优雅且省空间。迭代的思路是用一个哨兵虚拟头节点串联结果双指针各自前进每轮把值更小的节点接到结果链表的尾部。迭代版同样支持 CPP、JS、Java、Python 四种语言迭代 CPP Codeclass Solution { public: ListNode* mergeTwoLists(ListNode* a, ListNode* b) { ListNode head, *tail head; while (a b) { if (a-val b-val) { tail-next a; a a-next; } else { tail-next b; b b-next; } tail tail-next; } tail-next a ? a : b; return head.next; } };迭代 JS Codevar mergeTwoLists function (l1, l2) { const prehead new ListNode(-1); let prev prehead; while (l1 ! null l2 ! null) { if (l1.val l2.val) { prev.next l1; l1 l1.next; } else { prev.next l2; l2 l2.next; } prev prev.next; } prev.next l1 null ? l2 : l1; return prehead.next; };迭代 Java Codeclass Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode prehead new ListNode(-1); ListNode prev prehead; while (l1 ! null l2 ! null) { if (l1.val l2.val) { prev.next l1; l1 l1.next; } else { prev.next l2; l2 l2.next; } prev prev.next; } // 合并后 l1 和 l2 最多只有一个还未被合并完我们直接将链表末尾指向未合并完的链表即可 prev.next l1 null ? l2 : l1; return prehead.next; } }迭代 Python Codeclass Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) - ListNode: prehead ListNode(-1) prev prehead while l1 and l2: if l1.val l2.val: prev.next l1 l1 l1.next else: prev.next l2 l2 l2.next prev prev.next # 合并后 l1 和 l2 最多只有一个还未被合并完我们直接将链表末尾指向未合并完的链表即可 prev.next l1 if l1 is not None else l2 return prehead.next迭代解法的关键细节哨兵节点虚拟头prehead是一个值无关紧要通常取-1或0的虚拟节点用于简化对头节点的处理。最终返回prehead.next即真正的合并结果。这与 thinkings/linked-list.md 中总结的虚拟头技巧一致——它把头节点变成中间节点避免了对头节点的特殊判断循环条件while (l1 ! null l2 ! null)即只有两个链表都还有节点时才比较取值收尾拼接循环结束后l1和l2中最多只有一个还剩节点直接prev.next l1 null ? l2 : l1将剩余部分整体接上即可。迭代解法的时间复杂度同样是 $O(MN)$但空间复杂度降为 $O(1)$仅使用常数个指针这是相对递归解法的主要优势。延伸合并 K 个有序链表合并两个有序链表并不是终点。仓库中的 23.merge-k-sorted-lists.md 正是本题的直接进阶版——把合并两个推广到合并 K 个并借助分治 归并排序的思想将mergeTwoLists作为最小合并单元反复调用var mergeKLists function (lists) { // 图参考 https://zhuanlan.zhihu.com/p/61796021 if (lists.length 0) return null; if (lists.length 1) return lists[0]; if (lists.length 2) { return mergeTwoLists(lists[0], lists[1]); } const mid lists.length 1; const l1 []; for (let i 0; i mid; i) { l1[i] lists[i]; } const l2 []; for (let i mid, j 0; i lists.length; i, j) { l2[j] lists[i]; } return mergeTwoLists(mergeKLists(l1), mergeKLists(l2)); };可以看到mergeTwoLists在 23.merge-k-sorted-lists.md 中被作为核心原语复用了四次JS 的mergeTwoLists函数、Python 与 CPP 实现中的同名方法。这印证了一个规律吃透合并两个有序链表是攻克合并 K 个排序链表乃至归并排序类题目的前提。仓库的 collections/easy.md 收录列表和 SUMMARY.md 目录中都将本题编号 0021作为入门必刷题可见其基础地位。小结本文围绕 21.merge-two-sorted-lists.en.md 给出的题解系统梳理了 LeetCode 21 题的两种解法解法思路时间复杂度空间复杂度递归每次取出两链表头中较小者剩余部分递归合并$O(MN)$$O(MN)$递归栈迭代哨兵头 双指针逐节点拼接最后接上剩余链表$O(MN)$$O(1)$核心要点掌握链表节点的指针操作牢记两条边界某一链表为空、循环后收尾拼接递归重直观、迭代省空间。在此基础上可以自然地向 23. 合并 K 个排序链表 等归并类题目延伸将链表拼接这一考点彻底化为己用。赞分享文档教程知识库【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址https://gitcode.com/gh_mirrors/le/leetcode点击查看免费下载相关推荐LeetCode 21 合并两个有序链表Merge Two Sorted Lists题解递归与迭代双方案详解LeetCode 21 合并两个有序链表Merge Two Sorted Lists题解递归与迭代双方案详解 合并两个有序链表是链表类问题中最经典的入门题示例工程教程LeetCode-Go 题解21. Merge Two Sorted Lists 合并两个有序链表递归实现与源码剖析LeetCode Go 题解21. Merge Two Sorted Lists 合并两个有序链表递归实现与源码剖析 本文围绕 LeetCode 第 21示例工程LeetCode-Go 题解精讲合并两个有序链表Merge Two Sorted Lists递归实现剖析LeetCode Go 题解精讲合并两个有序链表Merge Two Sorted Lists递归实现剖析 本篇以 LeetCode Go https://示例工程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 21. 合并两个有序链表（Merge Two Sorted Lists）题解：递归与迭代双解法全解析
文档教程知识库【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址https://gitcode.com/gh_mirrors/le/leetcode点击查看免费下载本篇文章基于 leetcode 题解仓库中的 21.merge-two-sorted-lists.en.md 展开深入讲解合并两个升序链表的经典题LeetCode 第 21 题从问题建模、递归与迭代两种解法到复杂度分析并结合仓库中的链表专题与进阶题目 23. 合并 K 个排序链表帮助读者彻底掌握链表拼接这一类高频考点。题目描述将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例输入1-2-4, 1-3-4 输出1-1-2-3-4-4本题是 LeetCode 上典型的简单难度链表题但它几乎是所有归并类题目如归并排序、合并 K 个有序链表的最小原子操作值得把两种主流解法都吃透。前置知识解决本题之前建议先掌握两个核心概念递归链表天然具有递归结构用递归思想处理每次只比较两个头节点的问题非常直观链表数据结构理解节点valnext指针的组织方式、遍历与指针修改的基本操作。仓库中的 链表专题 thinkings/linked-list.md 系统总结了链表题的两个核心考点——指针的修改与链表的拼接并给出了一个原则画图、两个考点、三个注意、四个技巧的方法论。合并两个有序链表正是链表拼接考点最直接的代表题。解题思路本题可以使用递归来解将两个链表头部较小的一个与剩下的元素合并并返回排好序的链表头当两条链表中的一条为空时终止递归。把递归过程拆解来看若l1为空则直接返回l2剩下的元素全部来自l2若l2为空则直接返回l1否则比较两个头节点的值若l1.val l2.val则l1.next应该指向l1.next与l2合并后的结果返回l1否则l2.next应该指向l1与l2.next合并后的结果返回l2。也就是说递归函数每次只解决当前这一步谁当新链表的头剩余部分交给相同逻辑的递归调用去完成。由于两链表本身有序每次取出较小者就能保证最终结果是全局有序的。关键点掌握链表数据结构熟悉ListNode的定义val与next以及通过next指针遍历、拼接节点的基本操作考虑边界情况两条链表中有一条为空时包含一开始就为空、合并过程中提前耗尽两种情况递归直接返回另一条链表的剩余部分即可。代码实现递归解法仓库中的 21.merge-two-sorted-lists.en.md 提供了 CPP 与 JS 两种语言的递归实现中文版 21.merge-two-sorted-lists.md 还补充了 Java 与 Python 版本一并整理如下。CPP Codeclass Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (l1 nullptr) { return l2; } else if (l2 nullptr) { return l1; } else if (l1-val l2-val) { l1-next mergeTwoLists(l1-next, l2); return l1; } else { l2-next mergeTwoLists(l1, l2-next); return l2; } } };JS Code/** * Definition for singly-linked list. * function ListNode(val) { * this.val val; * this.next null; * } */ /** * param {ListNode} l1 * param {ListNode} l2 * return {ListNode} */ const mergeTwoLists function (l1, 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; } };Java Codeclass Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 null) { return l2; } else if (l2 null) { return l1; } else if (l1.val l2.val) { l1.next mergeTwoLists(l1.next, l2); return l1; } else { l2.next mergeTwoLists(l1, l2.next); return l2; } } }Python Codeclass Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) - ListNode: if not l1: return l2 # 终止条件直到两个链表都空 if not l2: return l1 if l1.val l2.val: # 递归调用 l1.next self.mergeTwoLists(l1.next, l2) return l1 else: l2.next self.mergeTwoLists(l1, l2.next) return l2复杂度分析设两条链表l1、l2的长度分别为M、N时间复杂度$O(MN)$。每次递归调用只处理一个节点合并过程中每个节点最多被访问一次空间复杂度$O(MN)$。递归深度取决于合并链表的长度最坏情况下需要消耗与节点总数等量的函数调用栈空间。需要说明的是递归解法在空间上并不占优。若对栈深度敏感例如链表很长、递归过深可能栈溢出应当改用下面介绍的迭代解法将空间复杂度降为 $O(1)$。扩展迭代解法递归写起来直观但迭代同样优雅且省空间。迭代的思路是用一个哨兵虚拟头节点串联结果双指针各自前进每轮把值更小的节点接到结果链表的尾部。迭代版同样支持 CPP、JS、Java、Python 四种语言迭代 CPP Codeclass Solution { public: ListNode* mergeTwoLists(ListNode* a, ListNode* b) { ListNode head, *tail head; while (a b) { if (a-val b-val) { tail-next a; a a-next; } else { tail-next b; b b-next; } tail tail-next; } tail-next a ? a : b; return head.next; } };迭代 JS Codevar mergeTwoLists function (l1, l2) { const prehead new ListNode(-1); let prev prehead; while (l1 ! null l2 ! null) { if (l1.val l2.val) { prev.next l1; l1 l1.next; } else { prev.next l2; l2 l2.next; } prev prev.next; } prev.next l1 null ? l2 : l1; return prehead.next; };迭代 Java Codeclass Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode prehead new ListNode(-1); ListNode prev prehead; while (l1 ! null l2 ! null) { if (l1.val l2.val) { prev.next l1; l1 l1.next; } else { prev.next l2; l2 l2.next; } prev prev.next; } // 合并后 l1 和 l2 最多只有一个还未被合并完我们直接将链表末尾指向未合并完的链表即可 prev.next l1 null ? l2 : l1; return prehead.next; } }迭代 Python Codeclass Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) - ListNode: prehead ListNode(-1) prev prehead while l1 and l2: if l1.val l2.val: prev.next l1 l1 l1.next else: prev.next l2 l2 l2.next prev prev.next # 合并后 l1 和 l2 最多只有一个还未被合并完我们直接将链表末尾指向未合并完的链表即可 prev.next l1 if l1 is not None else l2 return prehead.next迭代解法的关键细节哨兵节点虚拟头prehead是一个值无关紧要通常取-1或0的虚拟节点用于简化对头节点的处理。最终返回prehead.next即真正的合并结果。这与 thinkings/linked-list.md 中总结的虚拟头技巧一致——它把头节点变成中间节点避免了对头节点的特殊判断循环条件while (l1 ! null l2 ! null)即只有两个链表都还有节点时才比较取值收尾拼接循环结束后l1和l2中最多只有一个还剩节点直接prev.next l1 null ? l2 : l1将剩余部分整体接上即可。迭代解法的时间复杂度同样是 $O(MN)$但空间复杂度降为 $O(1)$仅使用常数个指针这是相对递归解法的主要优势。延伸合并 K 个有序链表合并两个有序链表并不是终点。仓库中的 23.merge-k-sorted-lists.md 正是本题的直接进阶版——把合并两个推广到合并 K 个并借助分治 归并排序的思想将mergeTwoLists作为最小合并单元反复调用var mergeKLists function (lists) { // 图参考 https://zhuanlan.zhihu.com/p/61796021 if (lists.length 0) return null; if (lists.length 1) return lists[0]; if (lists.length 2) { return mergeTwoLists(lists[0], lists[1]); } const mid lists.length 1; const l1 []; for (let i 0; i mid; i) { l1[i] lists[i]; } const l2 []; for (let i mid, j 0; i lists.length; i, j) { l2[j] lists[i]; } return mergeTwoLists(mergeKLists(l1), mergeKLists(l2)); };可以看到mergeTwoLists在 23.merge-k-sorted-lists.md 中被作为核心原语复用了四次JS 的mergeTwoLists函数、Python 与 CPP 实现中的同名方法。这印证了一个规律吃透合并两个有序链表是攻克合并 K 个排序链表乃至归并排序类题目的前提。仓库的 collections/easy.md 收录列表和 SUMMARY.md 目录中都将本题编号 0021作为入门必刷题可见其基础地位。小结本文围绕 21.merge-two-sorted-lists.en.md 给出的题解系统梳理了 LeetCode 21 题的两种解法解法思路时间复杂度空间复杂度递归每次取出两链表头中较小者剩余部分递归合并$O(MN)$$O(MN)$递归栈迭代哨兵头 双指针逐节点拼接最后接上剩余链表$O(MN)$$O(1)$核心要点掌握链表节点的指针操作牢记两条边界某一链表为空、循环后收尾拼接递归重直观、迭代省空间。在此基础上可以自然地向 23. 合并 K 个排序链表 等归并类题目延伸将链表拼接这一考点彻底化为己用。赞分享文档教程知识库【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址https://gitcode.com/gh_mirrors/le/leetcode点击查看免费下载相关推荐LeetCode 21 合并两个有序链表Merge Two Sorted Lists题解递归与迭代双方案详解LeetCode 21 合并两个有序链表Merge Two Sorted Lists题解递归与迭代双方案详解 合并两个有序链表是链表类问题中最经典的入门题示例工程教程LeetCode-Go 题解21. Merge Two Sorted Lists 合并两个有序链表递归实现与源码剖析LeetCode Go 题解21. Merge Two Sorted Lists 合并两个有序链表递归实现与源码剖析 本文围绕 LeetCode 第 21示例工程LeetCode-Go 题解精讲合并两个有序链表Merge Two Sorted Lists递归实现剖析LeetCode Go 题解精讲合并两个有序链表Merge Two Sorted Lists递归实现剖析 本篇以 LeetCode Go https://示例工程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考