LeetCode-Go 题解21. Merge Two Sorted Lists 合并两个有序链表递归实现与源码剖析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文围绕 LeetCode 第 21 题「Merge Two Sorted Lists」展开以 LeetCode-Go 仓库中 0021.Merge-Two-Sorted-Lists 目录的题解文档、Go 实现与单元测试为主体讲解如何用递归方式把两个升序链表合并为一个新链表并深入剖析ListNode数据结构、链表与切片互转的辅助函数以及测试用例的组织方式。读完本文你将掌握该题的递归解法原理、边界条件处理、复杂度分析并能直接复用仓库中的辅助函数在本地运行验证。题目描述原题要求参见 0021.Merge-Two-Sorted-Lists 题解文档Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.即合并两个有序链表返回一个新链表。新链表通过拼接两个输入链表的节点构成不新建节点数据而是直接复用原有节点进行串联。示例Input: 1-2-4, 1-3-4 Output: 1-1-2-3-4-4题目大意合并 2 个有序链表参见 README.md。解题思路原题解文档给出的思路非常简洁——Just follow the problem statement按照题意直接模拟即可。核心策略是两个链表都是升序的每次比较两个链表的头节点取较小者作为合并结果的当前节点将较小节点的Next指向剩余部分继续合并的结果当某一链表先被取空时直接把另一链表的剩余部分接到结果尾部。由于每一步都只处理当前两个头节点且剩余问题与原问题结构完全相同仍然是合并两个有序链表天然适合递归实现。Go 递归实现仓库中的完整实现位于 21. Merge Two Sorted Lists.go与题解文档中的代码一致package leetcode import ( github.com/halfrost/LeetCode-Go/structures ) // ListNode define type ListNode structures.ListNode /** * 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 } l2.Next mergeTwoLists(l1, l2.Next) return l2 }逐行解读空指针兜底if l1 nil { return l2 }与if l2 nil { return l1 }是递归的终止条件。当某一链表已遍历完时直接返回另一链表剩余部分即可这正是拼接splicing节点的体现——不复制节点直接复用原链表节点。递归选择较小头节点若l1.Val l2.Val说明l1的头节点应排在前面于是l1.Next指向「l1.Next与l2合并」的结果并返回l1否则对称处理l2。等值情形当l1.Val l2.Val时走else分支即优先选取l2的头节点。这与官方示例1-2-4, 1-3-4 1-1-2-3-4-4的排序语义一致等值元素谁先谁后均满足非降序要求。复杂度分析时间复杂度$O(m n)$其中 $m$、$n$ 分别为两个链表的长度。每个节点在递归中恰好被访问一次。空间复杂度$O(m n)$递归调用栈深度。若改为迭代写法空间复杂度可降至 $O(1)$这也是工程实现中更常见的选择递归写法胜在代码简洁、可读性高。递归执行过程演示以1-2-4与1-3-4为例递归展开如下mergeTwoLists(1-2-4, 1-3-4) l1.Val(1) l2.Val(1)不满足 走 else l2.Next mergeTwoLists(1-2-4, 3-4) l1.Val(1) l2.Val(3) → l1.Next mergeTwoLists(2-4, 3-4) → 返回 1-... 2 3 → l2.Next mergeTwoLists(4, 3-4)... ...依次归并最终得到 1-1-2-3-4-4链表数据结构与辅助函数题解代码通过type ListNode structures.ListNode将 structures 包 中的ListNode类型引入其定义位于 structures/ListNode.gotype ListNode struct { Val int Next *ListNode }该文件同时提供了一组链表与切片互转的辅助函数被测试代码大量使用Ints2List(nums []int) *ListNode把整数切片转换成单链表空切片返回nil。实现上先用哨兵节点l : ListNode{}统一追加逻辑最后返回l.Next作为真正的头节点。List2Ints(head *ListNode) []int把链表还原成整数切片。内部带有链条深度限制limit : 100遍历超过 100 个节点会panic并提示链条深度超过 100可能出现环状链条用于防止测试时误入环形链表导致死循环。单元测试与用例设计仓库为本题配备了完整的表驱动测试见 21. Merge Two Sorted Lists_test.go测试通过para21两个[]int参数与ans21期望的[]int结果组织用例func Test_Problem21(t *testing.T) { qs : []question21{ {para21{[]int{}, []int{}}, ans21{[]int{}}}, // 双空 {para21{[]int{1}, []int{1}}, ans21{[]int{1, 1}}}, // 等值单节点 {para21{[]int{1, 2, 3, 4}, []int{1, 2, 3, 4}}, ans21{[]int{1, 1, 2, 2, 3, 3, 4, 4}}}, {para21{[]int{1}, []int{9, 9, 9, 9, 9}}, ans21{[]int{1, 9, 9, 9, 9, 9}}}, // 长度悬殊 {para21{[]int{9, 9, 9, 9, 9}, []int{1}}, ans21{[]int{1, 9, 9, 9, 9, 9}}}, // 顺序对调 {para21{[]int{2, 3, 4}, []int{4, 5, 6}}, ans21{[]int{2, 3, 4, 4, 5, 6}}}, {para21{[]int{1, 3, 8}, []int{1, 7}}, ans21{[]int{1, 1, 3, 7, 8}}}, } // ... for _, q : range qs { _, p : q.ans21, q.para21 fmt.Printf(【input】:%v 【output】:%v\n, p, structures.List2Ints(mergeTwoLists(structures.Ints2List(p.one), structures.Ints2List(p.another)))) } }这些用例覆盖了本题的典型边界两个空链表返回空结果mergeTwoLists中两次nil判断返回nil单节点等值验证稳定输出1-1长度悬殊1与9,9,9,9,9及其对调版本验证某一链表先耗尽后剩余部分直接拼接等值交错2,3,4与4,5,6、1,3,8与1,7覆盖等值元素与大小交替插入的场景。运行go test ./leetcode/0021.Merge-Two-Sorted-Lists/ -v即可在本地复现上述用例输出。扩展从两两合并到合并 K 个有序链表mergeTwoLists也是 LeetCode 第 23 题「Merge k Sorted Lists」的基础。仓库中 0023.Merge-k-Sorted-Lists 的分治解法即把lists一分为二递归合并最终调用两个链表的合并逻辑完成归并func mergeKLists(lists []*ListNode) *ListNode { length : len(lists) if length 1 { return nil } if length 1 { return lists[0] } num : length / 2 left : mergeKLists(lists[:num]) right : mergeKLists(lists[num:]) // ... 最终调用两个有序链表的合并 }可见吃透mergeTwoLists的递归与边界处理是进一步掌握归并排序思想在链表上应用的基石。小结题解文档给出的递归解法按照题意模拟实现仅 6 行核心逻辑通过nil兜底 递归选小完成合并仓库源码 21. Merge Two Sorted Lists.go 复用 structures.ListNode 类型测试借助Ints2List/List2Ints完成链表与切片的双向转换测试用例覆盖双空、等值、长度悬殊、交错排序等边界场景可直接通过go test验证该解法同时是合并 K 个有序链表0023分治实现的基础值得深入理解。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考