企业官网建设流程全解析

• 示例工程
• 教程

本文基于 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）

思路分析

这是最直观、最稳妥的解法，核心思想可以概括为四句话：

1. 两链表各自有序，合并后仍须有序，每次取较小头结点接到结果后即可，无需再排序；
2. 用哑结点统一拼接，谁小接谁，剩余整段挂到末尾；
3. 先创建一个虚拟头结点dummy，再创建一个指针cur指向dummy；
4. 循环比较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.next

Python 版本中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 = (val===undefined ? 0 : val) * this.next = (next===undefined ? 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: Option<Box<ListNode>> // } // // impl ListNode { // #[inline] // fn new(val: i32) -> Self { // ListNode { // next: None, // val // } // } // } impl Solution { pub fn merge_two_lists( mut l1: Option<Box<ListNode>>, mut l2: Option<Box<ListNode>>, ) -> Option<Box<ListNode>> { 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 版本由于所有权的存在，是所有实现中写法最「绕」的一种：节点类型是Option<Box<ListNode>>，需要通过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 } }

边界情况小结（迭代法）

解法二：递归

思路分析

迭代已能线性完成，但实现稍长。递归的思路则更简洁：递归比较两头，较小者的next接到合并后的剩余部分，空间随递归深度增长。

具体步骤：

1. 先判断l1和l2中有没有一个为空，如果有一个为空，那么直接返回另一个链表即可；
2. 比较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 l2

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) { 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 = (val===undefined ? 0 : val) * this.next = (next===undefined ? 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: Option<Box<ListNode>> // } // // impl ListNode { // #[inline] // fn new(val: i32) -> Self { // ListNode { // next: None, // val // } // } // } impl Solution { pub fn merge_two_lists( l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>, ) -> Option<Box<ListNode>> { 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; } } }

两种解法对比与选型

实际面试中，两种写法都值得掌握：迭代版作为保底方案永远安全，递归版可作为亮点展示对递归思维的理解。递归版在 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]），建议对照阅读以强化对边界情况的理解。

实战延伸：这道题的价值在哪里

「合并两个有序链表」远不止是一道面试题，它是若干高频问题的基础积木：

1. 归并排序（链表版）：链表的归并排序正是「拆分成两半 → 递归排序 → 合并两个有序链表」三步，本解法直接构成 merge 步骤；
2. 合并 K 个有序链表：主站 23 题可通过两两合并（本解法）或优先队列求解，本解法是其中最朴素的一版；
3. 多路归并思想：外排序、数据库归并段合并等场景，底层都是把多个有序序列两两（或 K 路）归并成一个有序序列，本题正是最小规模的单元。

建议动手方式：先独立写出迭代版并通过示例用例（含1->2->4与1->3->4这类含重复值的用例，注意比较时使用<=以保证稳定性）验证；再写出递归版，并对比两种写法在「两条链表长度悬殊」时的行为差异。将两版代码分别与仓库目录下的Solution.*/Solution2.*源码核对，即可确认实现与官方题解完全一致。

• 示例工程
• 教程