type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 1:
示例 2:
示例 3:
提示:
k == lists.length
0 <= k <= $10^4$
0 <= lists[i].length <= 500
$10^4$ <= lists[i][j] <= $10^4$
lists[i]按 升序 排列
lists[i].length的总和不超过$10^4$
解法一:顺序两两合并
把结果
res看成一个累加器,依次与 lists[i] 合并。优点是简单,缺点是早期合并出的长链会被反复合并,导致多余工作。
复杂度
- 时间:最坏
O(nk)(新节点平均参与了 ~k/2 次合并),其中n为总节点数,k为链表条数
- 空间:
O(1)(不计递归;这里是纯迭代)
解法二:分治
把
k 条链表看成一个区间 lists[left … right]。拆分:把区间对半切成两段,分别递归得到“左半合并的结果”和“右半合并的结果”。
合并:把两条有序链表再进行一次标准的归并(
mergeTwoLists)。终止:当
left == right,区间里只有一条链表,直接返回它;当区间为空(初始就传空列表),返回 None。复杂度
- 时间:
O(n log k) - 每层递归:所有节点都经历一次“被归并到更大的链”的过程。
- 递归总层数:每次对半切,层数约为
log k。 - 总时间 ≈
log k层 × 每层O(n)=O(n log k)。
- 空间:
O(log k)(递归栈深度)
解法三:迭代版分治 (推荐)
仍然是基于分治的“同层对等合并”思路,但不用递归,而是Bottom-up地按层两两配对合并。

- 第 1 轮:
(list0,list1) → list0,(list2,list3) → list2,(list4,list5) → list4
- 第 2 轮:
(list0,list2) → list0
- 第 3 轮:
(list0,list4) → result
每一轮都把相邻的两条链表合成更长的一条,规模对半减少,直到收敛为 1 条。
它既保留了“合并均衡”的好处(所以仍是
O(n log k)),又避免了递归带来的栈开销。复杂度
- 时间:
O(n log k)(同样是log k层,每层线性时间)
- 空间:
O(1)(无递归栈)
解法四:最小堆
在任意时刻,只关心每条“尚未耗尽”的链表的当前最前节点。把这些“当前头节点”的键值放到一个最小堆里。
由于每条链表最多贡献一个候选,堆大小 ≤ k。
因为给的是K 个升序链表,所以堆中元素代表各条链表未合并的最小候选。
反复弹出堆顶的最小节点
x,把 x 接到已经合并排序的结果链表的尾部;若 x.next 存在,把 x.next 入堆,相当于替换了x。复杂度
- 时间:
O(n log k)(每个节点只入堆/出堆一次,代价是log k)
- 空间:
O(k)(堆中最多保留每条链的当前头部)
- Author:Fan Luo
- URL:https://fanluo.me/article/leetcode-23-合并-k-个升序链表
- Copyright:All articles in this blog adopt BY-NC-SA agreement. Please indicate the source!
上一篇
[Leetcode 21] 合并两个有序链表
下一篇
[Leetcode 25] K 个一组翻转链表