[Leetcode 23] 合并 K 个升序链表

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地按层两两配对合并
notion image
  • 第 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)(堆中最多保留每条链的当前头部)
 
上一篇
[Leetcode 21] 合并两个有序链表
下一篇
[Leetcode 25] K 个一组翻转链表