如何用小顶堆合并 K 个有序链表或数组？

简化版

把每一路当前的头元素放进小顶堆，每次弹出全局最小值接到结果后，再把它所在那一路的下一个元素放入堆。堆里最多 K 个元素，所以总复杂度是 O(N log K)。

详细版

合并 K 个有序链表/数组的关键是：每一路内部已经有序，当前全局最小值一定在 K 个“头元素”之中。因此不需要把所有元素一次性放进堆，只需要维护每一路的当前指针。

步骤：

初始化：每个非空链表的头节点入小顶堆。
循环：弹出堆顶节点，它是当前全局最小。
把该节点接到结果链表。
如果该节点有下一个节点，把下一个节点入堆。
直到堆为空。

ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
    for (ListNode head : lists) {
        if (head != null) pq.offer(head);
    }
    ListNode dummy = new ListNode(0), tail = dummy;
    while (!pq.isEmpty()) {
        ListNode node = pq.poll();
        tail.next = node;
        tail = tail.next;
        if (node.next != null) pq.offer(node.next);
    }
    return dummy.next;
}

如果总节点数为 N，链表数量为 K，每个节点进堆、出堆各一次，堆大小最多 K，所以时间 O(N log K)，空间 O(K)。

完整版教学

一、为什么全局最小只会出现在 K 个头里

每个链表或数组内部已经升序。对于某一路来说，如果当前头元素都不是全局最小，那么它后面的元素更不可能比当前头更小，因为后面只会更大。因此合并时只需要比较 K 个当前头元素，而不是比较所有剩余元素。

这个性质把问题从“所有 N 个元素中找最小”压缩成“每轮从 K 个候选中找最小”。小顶堆正是动态维护 K 个候选最小值的结构。弹出某一路头元素后，只有这一路的候选发生变化，补它的下一个元素即可。

L1: 1 -> 4 -> 7
L2: 2 -> 5 -> 8
L3: 3 -> 6 -> 9

候选头：1, 2, 3
弹出 1 后，L1 的候选变成 4
新候选：2, 3, 4

二、小顶堆保存的不是全部元素

很多人一看到堆就想把所有节点都放进去，这样也能得到正确答案，但会浪费空间。如果把 N 个节点全入堆，时间是 O(N log N)，空间是 O(N)；而 K 路合并只需要保留每一路一个候选，堆大小最多 K。

做法	堆中元素数	时间复杂度	空间复杂度	是否利用每路有序
全部入堆	N	`O(N log N)`	`O(N)`	否
K 个头入堆	K	`O(N log K)`	`O(K)`	是
分治两两合并	不用堆	`O(N log K)`	递归/迭代开销	是

如果 K=100、N=1,000,000，log K 远小于 log N，并且内存占用从百万级节点引用降到百级引用。面试官真正想听的是“利用每一路有序，只维护 K 个头”。

三、链表版本的指针细节

链表版本通常用 dummy 节点降低边界复杂度。每次 poll 出来的节点可以直接接到结果尾部，然后把它的 next 入堆。这里要注意：入堆的是原链表的下一个节点，不是结果链表的下一个位置。

while (!pq.isEmpty()) {
    ListNode node = pq.poll();
    tail.next = node;
    tail = node;
    if (node.next != null) {
        pq.offer(node.next);
    }
}

如果担心原链表指针残留造成理解混乱，可以在接入结果时暂存 next，再断开 node.next。多数在线题允许复用原节点，不要求新建节点；面试时说清楚“复用节点还是复制值”即可。

四、数组版本要在堆里存来源位置

数组没有链表指针，所以堆元素必须带上“来自哪一路、当前下标是多少”。弹出 (value, row, col) 后，如果 col + 1 没越界，就把同一路下一个元素入堆。这个状态扩展是很多堆题的通用套路。

堆元素 = (值, 第几路, 路内下标)

arrays:
A0 = [1, 4, 7]
A1 = [2, 5, 8]
A2 = [3, 6, 9]

初始堆：(1,0,0), (2,1,0), (3,2,0)
弹出 (1,0,0) 后加入 (4,0,1)

对于数组，结果通常是新数组；对于链表，结果可以复用节点。二者本质相同：堆里保存当前候选和“如何找到下一候选”的信息。

五、和分治合并怎么比较

堆法和分治法复杂度都可以做到 O(N log K)，但适用感不同。堆法是“每次从 K 路头中选最小”，适合流式输入、K 路来源动态变化、只想输出前若干个元素的情况。分治法是“两两合并”，代码在链表题里也很常见，适合静态 K 路全部已知。

堆法：
K 个当前头 -> 弹最小 -> 补同路下一个

分治：
K 条链表 -> 两两合并 -> K/2 条 -> ... -> 1 条

如果面试官追问“哪种更好”，不要只说复杂度一样。还要补充常数、实现复杂度、是否需要在线输出、是否容易处理数组/迭代器等工程条件。

六、常见误区与追问

记忆钩子：K 路合并的堆里只放 K 个“路口”，不是把整张地图都塞进去。

误区：要把所有节点一次性放入堆。 这样没错但没利用每路有序，空间和时间都更差。
误区：弹出节点后不用补新节点。 弹出某一路头后，该路的下一个元素就成了新候选，必须入堆。
误区：链表节点比较可以直接相减。 Java 中 a.val - b.val 可能溢出，更稳妥是 Integer.compare(a.val, b.val)。
追问：如果有空链表怎么办？ 初始化时跳过空头节点即可。
追问：如果只要最小的前 M 个结果呢？ 堆法可以提前停在 M 次弹出，分治通常会合完全部。
追问：复杂度为什么是 O(N log K)？ N 个元素各出堆一次，堆大小最多 K，每次调整 log K。

七、加强记忆

合并 K 路有序的关键是“每一路只暴露一个当前头”。因为每一路内部有序，全局最小一定在这些头元素里；弹出哪个头，就只补那一路的下一个。小顶堆负责在 K 个候选中快速找最小，dummy 节点负责让链表拼接不纠结头节点边界。记住“候选头入堆、弹出后补同路、堆大小最多 K”，就能把链表、数组、迭代器三类 K 路合并题统一起来。

简化版

详细版