京公网安备11010502063487号把两个升序链表合并成一个升序链表，新链表由原来两个链表的结点拼接而成。做法和归并排序的合并步骤一样：两个指针各指向一条链表的当前结点，每次取较小的接到结果后面，直到一条用完，再把另一条剩下的整体接上。本文用真实数据验证一个常见的说法：递归写法更简洁，但它在 Python 里会撞上递归深度限制；实测迭代解法的耗时，给出五种语言的实现，并把两个指针的移动过程做成分步演示。
完整题目见官方页面（链接在文末）。链表在测试里用整数数组表示，合并后的结果也用数组表示。基准解把两个数组拼起来直接排序，与指针拼接是两种独立的写法。一共 10 组用例，覆盖：官方示例、两条都为空、一条为空、两条互不交叉、大量重复值、含负数：
输入 [[1,2,4],[1,3,4]] 输出 [1,1,2,3,4,4] 输入 [[],[]] 输出 [] 输入 [[],[0]] 输出 [0] 输入 [[5],[]] 输出 [5] 输入 [[1,2,3],[4,5,6]] 输出 [1,2,3,4,5,6] 输入 [[4,5,6],[1,2,3]] 输出 [1,2,3,4,5,6]
递归写法很短：如果一条为空，返回另一条；否则取较小结点，让它的 next 指向"其余部分合并的结果"。每取一个结点就多一层递归，所以递归深度约等于合并后的结点总数。Python 默认的递归深度上限是 1000。下面是真实运行结果：
# 递归写法在 Python 里的深度限制（sys.getrecursionlimit() = 1000） 每条链表 100 个结点（合并后 200）: 递归 -> 成功，长度 200，结果正确=True 迭代 solve -> 长度 200 每条链表 400 个结点（合并后 800）: 递归 -> 成功，长度 800，结果正确=True 迭代 solve -> 长度 800 每条链表 500 个结点（合并后 1000）: 递归 -> RecursionError: maximum recursion depth exceeded 迭代 solve -> 长度 1000 每条链表 2000 个结点（合并后 4000）: 递归 -> RecursionError: maximum recursion depth exceeded 迭代 solve -> 长度 4000
每条链表 400 个结点（合并后 800）时递归写法正常，每条 500 个（合并后 1000）就抛出了 RecursionError。迭代写法不受影响。题目的官方限制是链表长度不超过 50，用递归不会有问题，但如果不知道输入规模，迭代更稳妥。Java、Go、C++ 也有栈深度限制，这里只在 Python 里做了实验。
先建一个哑结点，tail 指向结果链表的末尾。两个链表都不为空时，比较两个当前结点的值，取较小的接到 tail 后面，并让对应指针后移；相等时先取第一条，保证稳定。循环结束后至少有一条已经用完，把另一条整体接到 tail 后面即可，不用逐个比较。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def merge_two_lists(a, b): dummy = tail = ListNode() # 哑结点：省去"结果链表的头"的特判 while a and b: if a.val <= b.val: # 相等时先取 a，保证稳定 tail.next, a = a, a.next else: tail.next, b = b, b.next tail = tail.next tail.next = a or b # 剩下的一条整体接上，不用再逐个比较 return dummy.next
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[1,2,4],[1,3,4]] → [1,1,2,3,4,4] [[],[]] → [] [[],[0]] → [0] [[5],[]] → [5] [[1,2,3],[4,5,6]] → [1,2,3,4,5,6] [[4,5,6],[1,2,3]] → [1,2,3,4,5,6]
Java · 解法代码class ListNode { int val; ListNode next; ListNode(int v) { val = v; } } class Solution { public ListNode mergeTwoLists(ListNode a, ListNode b) { ListNode dummy = new ListNode(0), tail = dummy; // 哑结点：省去"结果链表的头"的特判 while (a != null && b != null) { if (a.val <= b.val) { tail.next = a; a = a.next; } // 相等时先取 a，保证稳定 else { tail.next = b; b = b.next; } tail = tail.next; } tail.next = a != null ? a : b; // 剩下的一条整体接上 return dummy.next; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[1,2,4],[1,3,4]] → [1,1,2,3,4,4] [[],[]] → [] [[],[0]] → [0] [[5],[]] → [5] [[1,2,3],[4,5,6]] → [1,2,3,4,5,6] [[4,5,6],[1,2,3]] → [1,2,3,4,5,6]
Go · 解法代码type ListNode struct { Val int Next *ListNode } func mergeTwoLists(a, b *ListNode) *ListNode { dummy := &ListNode{} // 哑结点：省去"结果链表的头"的特判 tail := dummy for a != nil && b != nil { if a.Val <= b.Val { // 相等时先取 a，保证稳定 tail.Next, a = a, a.Next } else { tail.Next, b = b, b.Next } tail = tail.Next } if a != nil { // 剩下的一条整体接上 tail.Next = a } else { tail.Next = b } return dummy.Next }
$ go build -o bin . && ./bin < cases.jsonl [[1,2,4],[1,3,4]] → [1,1,2,3,4,4] [[],[]] → [] [[],[0]] → [0] [[5],[]] → [5] [[1,2,3],[4,5,6]] → [1,2,3,4,5,6] [[4,5,6],[1,2,3]] → [1,2,3,4,5,6]
JavaScript · 解法代码class ListNode { constructor(val = 0, next = null) { this.val = val; this.next = next; } } function mergeTwoLists(a, b) { const dummy = new ListNode(); // 哑结点：省去"结果链表的头"的特判 let tail = dummy; while (a && b) { if (a.val <= b.val) { tail.next = a; a = a.next; } // 相等时先取 a，保证稳定 else { tail.next = b; b = b.next; } tail = tail.next; } tail.next = a || b; // 剩下的一条整体接上 return dummy.next; }
$ node run.js < cases.jsonl [[1,2,4],[1,3,4]] → [1,1,2,3,4,4] [[],[]] → [] [[],[0]] → [0] [[5],[]] → [5] [[1,2,3],[4,5,6]] → [1,2,3,4,5,6] [[4,5,6],[1,2,3]] → [1,2,3,4,5,6]
C++ · 解法代码struct ListNode { int val; ListNode* next; ListNode(int v) : val(v), next(nullptr) {} }; class Solution { public: ListNode* mergeTwoLists(ListNode* a, ListNode* b) { ListNode dummy(0); // 哑结点：省去"结果链表的头"的特判 ListNode* tail = &dummy; while (a && b) { if (a->val <= b->val) { tail->next = a; a = a->next; } // 相等时先取 a，保证稳定 else { tail->next = b; b = b->next; } tail = tail->next; } tail->next = a ? a : b; // 剩下的一条整体接上 return dummy.next; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[1,2,4],[1,3,4]] → [1,1,2,3,4,4] [[],[]] → [] [[],[0]] → [0] [[5],[]] → [5] [[1,2,3],[4,5,6]] → [1,2,3,4,5,6] [[4,5,6],[1,2,3]] → [1,2,3,4,5,6]
共 10 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 10/10 Java 通过 10/10 Go 通过 10/10 JavaScript 通过 10/10 C++ 通过 10/10
每条链表长度分别为 1000、10000、100000、300000，一条全是偶数、一条全是奇数，这是两个指针必须交替前进的情形。每个规模取三次中最快的一次：
每条链表的长度 | 暴力解 | 本文解法
1000 | 0.022 ms | 0.317 ms
10000 | 0.170 ms | 2.901 ms
100000 | 1.647 ms | 39.362 ms
300000 | 6.000 ms | 152.651 ms本文解法的耗时从 1000 到 10000（10 倍）增长约 9.2 倍，接近线性。这里"暴力解"是 Python 内置的 sorted(a + b)，它是 C 实现，而且能识别出输入里已有的有序段，所以比在 Python 里逐个结点操作的合并快得多（300000 时是 6.0ms 对 152.7ms）。这不说明链表合并慢，两者做的事情也不一样：solve 的耗时里还包含把数组建成链表、再把结果转回数组的开销，而 sorted 直接处理数组。这里的对比只能说明本文解法是线性增长，不能用来说明"链表合并比排序慢"。
Python 版本另外和"拼接后排序"做了随机对拍：
随机对拍 10000 组（两个长度 0 到 8 的有序数组（取值 -10 到 10，重复值很多）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 10 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 [1, 2, 4] 和 [1, 3, 4]。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。第一步两条链表都是 1，相等时取第一条的。