企业官网建设流程全解析

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"（按照题意直接模拟即可）。核心策略是：

1. 两个链表都是升序的，每次比较两个链表的头节点，取较小者作为合并结果的当前节点；
2. 将较小节点的Next指向剩余部分继续合并的结果；
3. 当某一链表先被取空时，直接把另一链表的剩余部分接到结果尾部。

由于每一步都只处理当前两个头节点，且剩余问题与原问题结构完全相同（仍然是"合并两个有序链表"），天然适合递归实现。

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.go：

type 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