合并 K 个升序链表：堆 vs 分治

一句话结论（30s）

合并 K 个升序链表的最优复杂度是 O(n log k)，因为每次只需从 K 个链表的当前头里取最小值，用大小为 k 的小顶堆维护这 K 个头即可，不需要一次性展开全部节点。

核心原理（2min）

两种做法：①小顶堆——各链表头入堆，反复 poll 最小节点并把其 next 入堆，O(n log k)/O(k)；②分治归并——两两归并，轮次 ⌈log₂k⌉，每轮总元素 n，O(n log k)/O(1)。dummy 节点统一追加逻辑，避免对结果链表首节点的特殊处理。

底层深入（5-10min）

方法一：小顶堆（更直观）

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(-1);
    ListNode cur = dummy;
    
    while (!pq.isEmpty()) {
        ListNode min = pq.poll();
        cur.next = min;
        cur = cur.next;
        if (min.next != null) pq.offer(min.next);  // 下一个元素入堆
    }
    
    return dummy.next;
}

💭 思考：看到什么信号该想到小顶堆？—— 题目让「反复从 K 个升序链表里取当前最小的头」，本质是「维护一组候选、每次都拿最小、拿了要补新候选」。这正好是堆的职责：取最小 O(1)、插入 O(log k)。为什么不用「每轮扫 K 个链表比大小」的暴力？因为那每次取最小要 O(k)，n 次就是 O(nk)；而堆把「比较」压到 O(log k)。信号是「动态候选 + 反复取最值」，套路是「大小为 k 的小顶堆维护各序列的头」。

堆中永远只有 k 个元素（每个链表在堆中只有一个当前最小节点）。每次 poll 一个最小值 → 将其下一个节点入堆。O(n log k)。为什么堆里只放 k 个头就够了？ 因为每个链表自身已经有序，全局最小值只可能出现在各链表”当前最靠前”的那个节点上；poll 掉一个就把它所在链表的下一个补进来，堆始终覆盖所有候选最小值。

方法二：分治归并（无需额外堆空间）

ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) return null;
    int interval = 1;  // 合并间隔
    while (interval < lists.length) {
        for (int i = 0; i + interval < lists.length; i += interval * 2) {
            lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
        }
        interval *= 2;  // 间隔翻倍
    }
    return lists[0];
}

💭 思考：为什么分治也是 O(n log k)，而且不用额外空间？—— 换个角度：不要「一次挑全局最小」，而是「把 K 个归并问题拆成两两归并」。既然两两合并（mergeTwoLists）是现成的、O(两链长度和)，那就让 K 条链表两两配对合并，一轮后剩下 k/2 条，再合并，直到 1 条——总共 ⌈log₂k⌉ 轮，每轮扫过的总节点数都是 n。所以「分治」的推导是从「已经会做两个」推广到「反复两两做」，用 log 轮把 k 消掉。

每轮两两合并，链表数减半：k → k/2 → k/4 → … → 1。共 ⌈log₂ k⌉ 轮，每轮的总元素都是 n，总 O(n log k)。空间 O(1)（复用输入数组）。

合并两个有序链表的 dummy 节点模板

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(-1);
    ListNode cur = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; }
        else                   { cur.next = l2; l2 = l2.next; }
        cur = cur.next;
    }
    cur.next = l1 != null ? l1 : l2;  // 剩余直接接上
    return dummy.next;
}

💭 思考：为什么链表题里老见到 dummy 节点？—— 想一下没有 dummy 时的两难：结果链表「第一个节点」是空的时候要单独建，之后每个节点又是「接到末尾」，两套逻辑。问题的根源是「头」和「身」被区别对待了。dummy 的招数是：造一个不存数据的假头，让「结果为空」也变成「已经有头了」，于是头身统一成「接到 cur.next」这一句。凡是链表需要「边遍历边追加」的题，先问一句「要不要 dummy 消除首节点特判」。

Dummy 节点避免了对”结果链表第一个节点”的特殊处理——所有节点统一追加到 cur.next。不设 dummy 会怎样？ 第一个节点要单独初始化 head，后续节点又要另一套追加逻辑，边界分支增多；dummy 让”结果为空”和”结果非空”共用同一段代码。

总结

章末提问

1. 合并 K 个链表为什么复杂度是 O(n log k) 而不是 O(nk)？ 结论：因为每次只从 K 个链表头里取一个最小值，用大小为 k 的堆维护这 K 个候选，取最小只需 O(log k)；n 个节点各取一次，故 O(n log k)，而不是每取一个都扫一遍 K 个链表的 O(nk)。

2. 堆解法里，poll 出一个节点后为什么要把它 next 入堆？ 结论：因为当前最小值被取出后，它所在链表的”下一个节点”才成为新的候选头；不补进去就会丢掉这条链表后续的所有元素。

3. 分治归并和小顶堆两种解法各有什么取舍？ 结论：两者时间都是 O(n log k)，但堆用 O(k) 额外空间、实现直观；分治归并复用两两合并、空间 O(1) 但思路稍绕。