代表性面试主题

算法面试：如何合并 K 个有序链表？

编程题困难
OfferCC 编辑团队发布 更新

题干

给定 k 个按非递减顺序排列的单链表，请把它们合并成一个有序链表。要求复用现有节点，处理空链表和重复值，目标时间 O(N log k)、辅助空间 O(k)，并解释正确性、相等值处理、替代方案和边界用例。

题干与适用场景

给定数组 lists，其中保存 k 个单链表的头节点。请把全部节点合并成一个按非递减顺序排列的 链表。任意输入链表都可能为空，数值可以为负数或重复值，所有输入节点总数记为 N。

假设每个输入链表无环、已经有序，且不同输入不共享节点。实现可以重新连接现有节点，不能为每个 数值都创建替代节点。不同输入链表中的相等值不要求保持特定顺序。数组为空或所有头节点都是 None 时返回 None。目标时间为 O(N log k)，辅助空间为 O(k)。

text
Input:
  1 -> 4 -> 5
  1 -> 3 -> 4
  2 -> 6

Output:
  1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

这是一道链表题，因此指针所有权也是契约的一部分。如果调用方要求输入链表保持不变，算法选择 可以不变，但输出必须创建 N 个新节点，输出空间会变为 O(N)。

面试官考察点

第一项信号是能否利用输入已有序。把全部值摊平后排序可以得到正确结果，但需要 O(N log N) 时间和 O(N) 额外存储。每输出一个节点就扫描全部当前头节点，虽然利用了有序性，仍需 O(Nk)。强回答会先问：下一个全局最小值可能落在哪个小集合中？

第二项信号是候选头节点不变量。对每条未耗尽链表，只有第一个尚未合并的节点可能成为下一个 输出；因为链表有序，它后面的每个节点都不小于这个头节点。因此，最小堆只需保存每条未耗尽 链表的一个候选头，就能把最多 k 个候选的线性扫描变成大小不超过 k 的堆删除与插入。

第三项信号是证明和复杂度核算。回答应说明：选出的节点为什么是全局最小值、为什么只压入它的 后继就能恢复不变量、为什么每个节点恰好输出一次，以及堆为什么不会超过非空链表数。只说“用 优先队列”没有展示核心推导。

第四项信号是实现细节。在 Python 中，如果两个堆条目的数值优先级相同，元组比较不能继续比较 ListNode 对象。加入唯一序号可以消除这个问题。复用节点时，代码先保存原后继，再断开并追加 当前节点，使已构造前缀只有一个明确所有者，不会临时指向尚未合并的链表。

最后一项信号是能否在两种最优方案间做选择。最小堆和均衡两两合并都能达到 O(N log k)。 最小堆把候选集合写得更明确，也容易扩展到迭代器或流；分治只使用普通的双链表合并，在保存头 节点的数组之外可以只用常数级指针空间。应根据输入契约选择更容易解释的方案。

回答前需要澄清的问题

  • 可以修改并复用输入节点吗？ 可以就重新连线，只保留 O(k) 堆状态；不可以就创建输出

节点，并把 O(N) 输出空间与算法辅助状态分开汇报。

  • 所有输入都保证有序且无环吗？ 基础算法依赖这两点。验证有序性需要 O(N)，检测环也会

增加工作，不能默认塞进基础解法。

  • k 具体计算什么？ 令 m 为非空链表数。堆最多保存 m 个元素，因此 m >= 2 时更

精确的界是 O(N log m)，零或一条非空链表时为线性。

  • 相等值是否要保持跨链表顺序？ 基础题只要求数值有序。稳定性契约必须先定义来源顺序，再

把它编码进堆键。

  • 可以使用语言标准库的优先队列吗？ 除非面试官还要单独考察堆实现，通常可以。应先确认，

不要直接花面试时间手写二叉堆。

  • 输入是完整链表还是惰性迭代器？ 最小堆都能处理，但迭代器版本只能在当前值被取出后推进

对应来源。

  • 输入头节点数组应保持什么状态？ 下面的代码不会修改数组项，但会重新连接其中的节点。

如果调用方同时观察两者，应明确这是所有权转移。

30 秒回答框架

“每条有序链表只有第一个未合并节点可能成为下一个全局最小值，所以我会把这些候选头节点放入 最小堆。每次弹出最小节点并追加到结果，然后只压入它保存下来的后继。不变量是：堆恰好包含每条 未耗尽链表的一个候选头；因此弹出的节点一定安全，补上其来源的后继又恢复不变量。N 个节点各 弹出一次，最多各压入一次，堆大小不超过 k，所以时间是 O(N log k)，辅助空间是 O(k)。 实现会复用节点，加入唯一序号防止相等值触发节点对象比较，并测试空输入、重复值、负数、长度 差异和单链表。主要替代方案是同复杂度的均衡两两合并。”

分步骤深入解答

先列出直接方案，找到重复工作：

方案时间辅助空间重复或丢弃的信息
摊平数值、排序、重建O(N log N)O(N)丢弃每个输入已经有序这一条件
每个节点扫描最多 k 个头O(Nk)O(1)重复执行 N 次线性最小值查找
逐条合并进累积结果最坏 O(Nk)O(1)早期节点在后续合并中反复遍历
均衡两两合并O(N log k)O(1) 指针空间每一层合并处理全部节点一次
候选头最小堆O(N log k)O(k)通过堆操作选择下一个来源

顺序合并的成本容易被低估。假设 k 条链表长度接近 L，工作量按 2L + 3L + ... + kL 增长，即 O(Lk²)。因为 N = Lk，所以最坏为 O(Nk)。两两合并 通过分轮保持平衡，每个节点最多参加 ceil(log₂ k) 层合并，避免不断增长的累积结果。

对最小堆方案，在每次删除堆顶前维持下面的不变量：

text
For each non-exhausted input list:
  the heap contains exactly its first unmerged node.

For each exhausted input list:
  the heap contains no node from that list.

The result contains every previously removed node exactly once,
in non-decreasing order.

初始化把每个非空头节点压入堆，因此不变量成立。假设某轮开始时不变量成立。任何未合并节点要么 是堆中的候选头，要么位于某个候选头之后。因为每条输入有序，更深的节点不可能小于该候选头。 所以堆中最小条目不大于任何未合并节点，可以安全追加。

取出节点后，只有它所属链表失去代表。先保存该节点的原后继，断开并追加该节点；如果后继存在， 就把后继压入堆。其他来源的候选头保持有效，不变量恢复。每轮输出一个节点，恰好 N 轮后所有 链表耗尽、堆为空，由此证明结果有序、节点完整且算法终止。

下面的 Python 实现把单调递增序号放在元组第二项。序号唯一，所以数值相等时，元组比较不会 继续到不可排序的节点对象。

python
from __future__ import annotations

from dataclasses import dataclass
from heapq import heappop, heappush
from itertools import count


@dataclass
class ListNode:
    val: int
    next: ListNode | None = None


def merge_k_lists(lists: list[ListNode | None]) -> ListNode | None:
    heap: list[tuple[int, int, ListNode]] = []
    sequence = count()

    for head in lists:
        if head is not None:
            heappush(heap, (head.val, next(sequence), head))

    dummy = ListNode(0)
    tail = dummy

    while heap:
        _, _, node = heappop(heap)
        next_node = node.next
        node.next = None
        tail.next = node
        tail = node

        if next_node is not None:
            heappush(heap, (next_node.val, next(sequence), next_node))

    return dummy.next

初始有 m 次插入，其中 m <= k 是非空链表数。每个节点删除一次，除各链表尾节点外，每个 节点还可能引发一次后继插入。堆最多有 m 个条目，操作成本为 O(log m)。m >= 2 时总时间 为 O(N log m)，通常写作 O(N log k)；m <= 1 时遍历为 O(N)。堆、序号计数器、哑节点 和指针使用 O(m) 辅助空间。返回的是原节点，不属于新增算法存储。

断开 node.next 不会丢失后继，因为后继已先保存。这样已合并前缀不会临时指向尚未赢得堆选择 的来源节点，指针所有权更清楚。下一次追加会为尾节点设置新后继。在无环且各输入节点互不共享的 契约下，算法不会修改数值，也不会重复压入同一个节点。

测试应覆盖结构，而不只覆盖一组正常数值：

python
def build(values: list[int]) -> ListNode | None:
    dummy = ListNode(0)
    tail = dummy
    for value in values:
        tail.next = ListNode(value)
        tail = tail.next
    return dummy.next


def values(head: ListNode | None) -> list[int]:
    result: list[int] = []
    while head is not None:
        result.append(head.val)
        head = head.next
    return result


cases = [
    ([], []),
    ([[]], []),
    ([[1, 4, 5], [1, 3, 4], [2, 6]], [1, 1, 2, 3, 4, 4, 5, 6]),
    ([[], [-3, -1, 2], [], [-3, 7]], [-3, -3, -1, 2, 7]),
    ([[5]], [5]),
]

for raw_lists, expected in cases:
    actual = values(merge_k_lists([build(items) for items in raw_lists]))
    assert actual == expected, (raw_lists, expected, actual)

生产级验证还应记录所有输入节点的身份，用 visited 集合遍历输出，并证明三件事：没有环、恰好有 N 个不同节点身份、相邻数值非递减。这能发现只比较数值时可能遗漏的重复插入、节点丢失和指针环。

当面试官重点考察指针操作、没有优先队列，或希望减少堆存储时，选择均衡两两合并。当来源以 迭代器形式提供、活跃来源数会变化，或明确展示“下一个全局候选”的机制更易理解时，选择最小堆。 在基础契约下两者都是正确的最优回答，关键是说明选择理由。

高质量示范回答

“我会复用输入节点，并假设每条链表有序、无环且互不共享。令 N 为总节点数、m 为非空链表 数。下一个输出只可能是 m 个当前头节点之一，因为更深的节点不小于所在链表的头。因此我会把 每条非空链表的一个头节点放进最小堆。

不变量是：堆恰好包含每条未耗尽链表的第一个未合并节点，输出包含所有已弹出节点且保持有序。 每次删除最小项，保存并断开它的后继，追加当前节点，再压入后继。弹出节点一定安全，因为其他 任何未合并节点都位于某个不大于它的堆候选之后；补入后继又恢复每条链表一个候选的不变量。

Python 堆条目写成 (value, sequence, node)。唯一序号避免相等优先级继续比较节点对象；题干 没有要求跨链表稳定顺序，所以不额外声称稳定性。每个节点弹出一次、最多压入一次，堆最多有 m 项，因此时间是 O(N log m)，通常写作 O(N log k)，辅助空间是 O(m)；零或一条非空 链表时为线性。

我会测试空数组、全部为空、单链表、长度差异、负数和相等值。因为解法重新连接指针，还会验证 节点身份和无环。均衡两两合并是主要替代方案，同样是 O(N log k)，只使用双链表合并原语； 如果题目重点是指针实现或禁止标准库堆，我会选择它。”

常见错误

  • 直接摊平并排序 → 忽略输入已有序，花费 O(N log N) 和输出存储 → **维护每个有序来源

的一个候选头。**

  • 每个节点都扫描 k 个头 → 最小值选择变成 O(Nk) → **使用大小不超过 k 的最小堆

或均衡两两合并。**

  • 依次合并进不断增长的结果 → 早期节点在之后多次被遍历 → 按轮次均衡合并。
  • 把所有节点都压入堆 → 堆增至 N，工作退化为 O(N log N) → **每个来源只压入一个当前

节点。**

  • Python 堆保存 (value, node) → 相等值会比较不可排序的节点对象 → 加入唯一数值序号。
  • 保存后继之前就推进或改线 → 可能丢失剩余链表 → 先保存后继，再断开并追加。
  • 因为复用节点就声称 O(1) 空间 → 堆仍保存最多 k 个条目 → **分开核算输出分配和辅助

状态。**

  • 只验证输出数值 → 环、重复节点或节点丢失可能未被发现 → **检查节点身份、数量、有序性和

无环。**

  • 没有确认就加入排序与环检测 → 实现扩大了契约并改变成本 → **先声明假设，只在要求时增加

验证。**

追问及应对

为什么堆顶就是下一个全局最小值？

每条未耗尽有序链表提供第一个未合并节点。其他节点都位于某个候选头之后，不可能小于这个候选 头。因此，最小候选头不大于任何未合并节点。弹出它是安全的，压入它的后继就恢复该来源的覆盖。

如果相等值必须按输入链表顺序稳定输出，怎么改？

先精确定义稳定性，再把堆键写成数值加来源链表下标。因为每个来源同时只有一个节点在堆中， 来源下标解决跨链表相等值，链表内部顺序天然保持。基础实现中的序号只保证可比较性，不保证这项 更强策略。

什么时候分治优于最小堆？

已经有双链表合并、面试重点是指针操作，或不能用优先队列时，采用均衡两两合并。每轮处理一次 全部剩余节点，共 O(log k) 轮。对于惰性来源和活跃来源数变化，最小堆更直接。

如果输入链表必须保持不变呢？

保留相同的候选选择逻辑，但每弹出一个数值就创建新节点。时间仍为 O(N log k)。候选选择状态 仍是 O(k)，必要的输出分配是 O(N)；两项应分别说明，不能把输出空间隐藏掉。

如果有一万个链表槽位，但只有五条非空呢？

初始化需要扫描一次 k 个槽位，之后堆最多只有 m = 5 项。精确时间为 O(k + N log m)，辅助空间为 O(m)。只写 O(N log k) 仍是安全上界，但没有体现跳过空头 节点的收益。

如果输入是有序迭代器而不是链表呢？

从每个非空迭代器读取一个值，与来源身份一起放入堆。产出最小值后只推进该来源并插入下一个值。 候选头证明不变，结果可以惰性生成，内存与活跃来源数成正比，而不是与总数值数成正比。

弹出节点有后继时，可以使用 heapreplace 吗？

如果已经单独执行 heappop，旧堆顶已经离开，不能再 replace。另一种实现可以先查看堆顶，在 该来源有后继时一次替换；来源耗尽时仍需单独分支。面试中先弹出再压入更容易证明，渐进复杂度 相同。

除了示例，怎样测试指针正确性？

合并前保存每个输入节点身份。遍历结果时拒绝重复身份，确认恰好 N 个节点、每对相邻值有序， 且身份集合完全相同。再随机生成有序链表，把结果数值与可信的摊平排序 oracle 比较；oracle 用于 测试，不代表生产解法复杂度。

公开来源

Merge K Sorted Lists

Hello Interview

Merge k Sorted Lists

LeetCode

Frustrated

Reddit / r/leetcode

heapq — Heap Queue Algorithm

Python Software Foundation

MinPQ.java

Princeton University Algorithms, 4th Edition

COS 226 Assignment 2: Sorting, Merging, Heaping

Princeton University

同类题目

算法面试：如何用双指针解决接雨水？查看问题与回答算法面试：如何实现 Dijkstra 最短路径算法？查看问题与回答算法面试：如何实现并查集并维护连通分量？查看问题与回答

相关面试工具

用 Screenshot 处理算法题

截图题目后，按顺序看约束、解法、代码、边界条件和复杂度。

查看工具
免费注册