合并 K 个升序链表 图解题解

从合并两条到合并 K 条，难在哪里

合并两条有序链表时，每一步只需比较两个头节点、取小的接走。链表变成 K 条后，问题的本质没变——结果链的下一个节点，永远是「K 个当前头里最小的那个」。难点只剩一个：怎么快速地从 K 个候选里反复取最小。每次线性扫一遍 K 个头要 O(K)，N 个节点总共就是 O(NK)，链表条数一多就顶不住了。

为什么逐条合并和全量排序都不划算

一个直觉做法是把第一条和第二条合并，结果再和第三条合并，如此推进。问题在于结果链越合越长，靠前的节点会被反复扫描，最坏总代价同样是 O(NK)。另一个做法是把所有节点值收进数组排序再重建链表，时间 O(N log N)、还要 O(N) 空间，而且完全没利用「每条链本来就有序」这个现成条件——有序意味着全局最小的候选其实只有 K 个头，这条信息被白白浪费了。

为什么最小堆正好卡在这个需求上

「维护一批候选、随时弹出最小、随时补充新候选」正是最小堆（优先队列）的本职：弹出和插入都只要 O(log K)。做法是先把 K 条链的头节点全部入堆，循环里弹出堆顶接到结果链尾部，若被弹出的节点还有后继，就把后继入堆，堆空时合并结束。

整个过程保持一个不变量：堆里装的恰好是每条还没走完的链的当前头。有了这个不变量，堆顶必然是所有剩余节点的全局最小，每次接走堆顶，结果链自然严格升序，正确性就立在这里。

为什么弹出一个只需要补一个

某条链的头被取走后，这条链新的最小值就是原头的 next——链本身有序保证了这一点，更靠后的节点不可能抢在 next 前面成为候选。所以每弹一个只补一个，堆的大小始终不超过 K。这也解释了一个常见错误：把所有节点一次性全塞进堆，结果虽然也对，但堆膨胀到 N 个元素，时间退化成 O(N log N)，空间从 O(K) 涨到 O(N)，最小堆的精髓恰恰在于堆要小。

不用堆还能怎么做：分治两两归并

分治是等价的另一条路：把 K 条链两两配对合并成约一半，再两两合并，重复 log K 轮；每一轮所有节点被扫一遍，总时间同样 O(N log K)，额外空间只有递归栈。两种写法复杂度相同，堆版思路更直白，分治版不依赖堆结构，面试时任选其一并能说出另一种，是很好的加分点。

复杂度与容易翻车的细节

堆版总时间 O(N log K)：N 个节点各入堆、出堆一次，每次堆操作 O(log K)；空间 O(K)。三个细节：入堆前要跳过空链表，空节点入堆会直接报错；弹出后忘记补后继，那条链剩下的节点就永远丢了；Python 里两个链表节点对象不能直接比较大小，堆元素要写成「值、链序号、节点」三元组，值相等时靠序号打破平局。

Python

import heapq
def mergeKLists(lists):
    h = []                       # 最小堆，元素 (值, 链序号, 节点)
    for i, node in enumerate(lists):
        if node: heapq.heappush(h, (node.val, i, node))
    dummy = tail = ListNode()
    while h:
        val, i, node = heapq.heappop(h)   # 弹最小
        tail.next = node; tail = node
        if node.next:                     # 补后继
            heapq.heappush(h, (node.next.val, i, node.next))
    return dummy.next

C++

struct Cmp { bool operator()(ListNode* a, ListNode* b){ return a->val > b->val; } };
ListNode* mergeKLists(vector<ListNode*>& lists){
    priority_queue<ListNode*, vector<ListNode*>, Cmp> h;
    for(auto n : lists) if(n) h.push(n);
    ListNode dummy, *tail = &dummy;
    while(!h.empty()){
        ListNode* node = h.top(); h.pop();   // 弹最小
        tail->next = node; tail = node;
        if(node->next) h.push(node->next);   // 补后继
    }
    return dummy.next;
}

Java

public ListNode mergeKLists(ListNode[] lists){
    PriorityQueue<ListNode> h =
        new PriorityQueue<>((a, b) -> a.val - b.val);  // 最小堆
    for(ListNode n : lists) if(n != null) h.offer(n);
    ListNode dummy = new ListNode(0), tail = dummy;
    while(!h.isEmpty()){
        ListNode node = h.poll();             // 弹最小
        tail.next = node; tail = node;
        if(node.next != null) h.offer(node.next);  // 补后继
    }
    return dummy.next;
}