京公网安备11010502063487号给定 k 个升序链表，把它们合并成一个升序链表。最直接的想法是依次把每条链表合并到结果里，但结果越来越长，前面的结点会被反复比较。常见的更好做法有两种：用最小堆每次取出 k 个链表头里最小的；或者分治，两两合并再逐轮合并。本文选分治，因为它只需要上一题的"合并两个链表"，五种语言都不需要另写堆。用真实数据比较顺序合并和分治合并，给出五种语言的实现，并把合并的轮次做成分步演示。
完整题目见官方页面（链接在文末）。链表在测试里用整数数组表示，输入是若干个数组，结果是一个数组。基准解把所有元素拉平后直接排序，与链表合并是两种独立的写法。一共 10 组用例，覆盖：官方示例、没有链表、只有一条空链表、全是空链表、只有一条链表、多条相同的链表、空链表夹在中间：
输入 [[[1,4,5],[1,3,4],[2,6]]] 输出 [1,1,2,3,4,4,5,6] 输入 [[]] 输出 [] 输入 [[[]]] 输出 [] 输入 [[[],[]]] 输出 [] 输入 [[[1]]] 输出 [1] 输入 [[[1],[1],[1]]] 输出 [1,1,1]
顺序合并是把第 1 条并入结果、再把第 2 条并入结果……每次合并的长度是已经合并好的部分加上新的一条，总共约 k²·m/2 次比较（m 是每条的长度）。分治合并每一轮总的处理量是全部结点数 N，一共约 log k 轮，总共 N log k。下面每条链表 20 个结点，k 从 50 增加到 3200，每个规模取三次中最快的一次，两种写法结果一致：
每条链表 20 个结点，k 条链表：逐条顺序合并 vs 分治合并（每个规模取三次中最快） k= 50: 顺序合并 0.86 ms 分治合并 0.27 ms 结果一致=True k= 200: 顺序合并 13.00 ms 分治合并 1.54 ms 结果一致=True k= 800: 顺序合并 198.71 ms 分治合并 7.35 ms 结果一致=True k= 3200: 顺序合并 3799.00 ms 分治合并 40.44 ms 结果一致=True
k 从 800 到 3200（4 倍）时，顺序合并的耗时增长约 19 倍，接近平方增长（16 倍）；分治合并增长约 5.5 倍，略高于线性（4 倍），符合 N log k。k = 3200 时，顺序合并用了 3.8 秒，分治合并只用了 40ms，约 94 倍。
merge(lo, hi) 返回第 lo 到第 hi 条链表合并后的结果：只有一条就直接返回；否则合并左半和右半各自的结果，再把这两个结果合并。合并两条链表就是上一题的做法。没有链表时 lo > hi，返回空链表。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def merge_two(a, b): dummy = tail = ListNode() while a and 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 or b return dummy.next def merge_k_lists(lists): def merge(lo, hi): # 分治：先各自合并左半和右半，再合并这两个结果 if lo > hi: return None if lo == hi: return lists[lo] mid = (lo + hi) // 2 return merge_two(merge(lo, mid), merge(mid + 1, hi)) return merge(0, len(lists) - 1)
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[[1,4,5],[1,3,4],[2,6]]] → [1,1,2,3,4,4,5,6] [[]] → [] [[[]]] → [] [[[],[]]] → [] [[[1]]] → [1] [[[1],[1],[1]]] → [1,1,1]
Java · 解法代码class ListNode { int val; ListNode next; ListNode(int v) { val = v; } } class Solution { public ListNode mergeKLists(ListNode[] lists) { return merge(lists, 0, lists.length - 1); } private ListNode merge(ListNode[] lists, int lo, int hi) { // 分治：先各自合并左半和右半，再合并这两个结果 if (lo > hi) return null; if (lo == hi) return lists[lo]; int mid = (lo + hi) >>> 1; return mergeTwo(merge(lists, lo, mid), merge(lists, mid + 1, hi)); } private ListNode mergeTwo(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; } 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,4,5],[1,3,4],[2,6]]] → [1,1,2,3,4,4,5,6] [[]] → [] [[[]]] → [] [[[],[]]] → [] [[[1]]] → [1] [[[1],[1],[1]]] → [1,1,1]
Go · 解法代码type ListNode struct { Val int Next *ListNode } func mergeTwo(a, b *ListNode) *ListNode { dummy := &ListNode{} tail := dummy for a != nil && b != nil { if a.Val <= b.Val { 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 } func mergeKLists(lists []*ListNode) *ListNode { var merge func(lo, hi int) *ListNode // 分治：先各自合并左半和右半，再合并这两个结果 merge = func(lo, hi int) *ListNode { if lo > hi { return nil } if lo == hi { return lists[lo] } mid := (lo + hi) / 2 return mergeTwo(merge(lo, mid), merge(mid+1, hi)) } return merge(0, len(lists)-1) }
$ go build -o bin . && ./bin < cases.jsonl [[[1,4,5],[1,3,4],[2,6]]] → [1,1,2,3,4,4,5,6] [[]] → [] [[[]]] → [] [[[],[]]] → [] [[[1]]] → [1] [[[1],[1],[1]]] → [1,1,1]
JavaScript · 解法代码class ListNode { constructor(val = 0, next = null) { this.val = val; this.next = next; } } function mergeTwo(a, b) { const dummy = new ListNode(); let tail = dummy; 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 || b; return dummy.next; } function mergeKLists(lists) { const merge = (lo, hi) => { // 分治：先各自合并左半和右半，再合并这两个结果 if (lo > hi) return null; if (lo === hi) return lists[lo]; const mid = (lo + hi) >> 1; return mergeTwo(merge(lo, mid), merge(mid + 1, hi)); }; return merge(0, lists.length - 1); }
$ node run.js < cases.jsonl [[[1,4,5],[1,3,4],[2,6]]] → [1,1,2,3,4,4,5,6] [[]] → [] [[[]]] → [] [[[],[]]] → [] [[[1]]] → [1] [[[1],[1],[1]]] → [1,1,1]
C++ · 解法代码#include <vector> using namespace std; struct ListNode { int val; ListNode* next; ListNode(int v) : val(v), next(nullptr) {} }; class Solution { ListNode* mergeTwo(ListNode* a, ListNode* b) { ListNode dummy(0); ListNode* tail = &dummy; 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 dummy.next; } ListNode* merge(vector<ListNode*>& lists, int lo, int hi) { // 分治：先各自合并左半和右半，再合并这两个结果 if (lo > hi) return nullptr; if (lo == hi) return lists[lo]; int mid = (lo + hi) / 2; return mergeTwo(merge(lists, lo, mid), merge(lists, mid + 1, hi)); } public: ListNode* mergeKLists(vector<ListNode*>& lists) { return merge(lists, 0, (int)lists.size() - 1); } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[[1,4,5],[1,3,4],[2,6]]] → [1,1,2,3,4,4,5,6] [[]] → [] [[[]]] → [] [[[],[]]] → [] [[[1]]] → [1] [[[1],[1],[1]]] → [1,1,1]
共 10 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 10/10 Java 通过 10/10 Go 通过 10/10 JavaScript 通过 10/10 C++ 通过 10/10
每条链表 20 个结点，k 分别为 100、1000、5000、20000，链表是交错的（第 i 条是 i、i+k、i+2k……）：
链表条数 k（每条 20 个结点） | 暴力解 | 本文解法
100 | 0.139 ms | 0.717 ms
1000 | 1.004 ms | 10.176 ms
5000 | 5.356 ms | 58.133 ms
20000 | 20.711 ms | 395.029 ms本文解法从 5000 到 20000（4 倍）耗时增长约 6.8 倍，符合 N log k 略高于线性的预期。这里"暴力解"是 Python 内置的 sorted，是 C 实现，而且能识别已有序的片段，所以更快；同时 solve 的耗时里还包含把数组建成链表、再把结果转回数组的开销，所以这个对比不能说明链表合并慢，只能说明本文解法的增长趋势。
Python 版本另外和"拉平后排序"做了随机对拍：
随机对拍 5000 组（0 到 9 条链表、每条长度 0 到 6、取值 -10 到 10（包含空链表、没有链表、大量重复值）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 10 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用 4 条链表 [1, 4, 5]、[1, 3, 4]、[2, 6]、[0, 7]。每一步都真实调用了上面的合并函数，运行器还检查了最终结果与 solve 的返回值一致。第 1 轮把 4 条两两合并成 2 条，第 2 轮再合并成 1 条。