#23

困难

高频

优先队列

合并K个排序链表

这是一道围绕链表、数组、排序展开的高频练习。建议先掌握「优先队列」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

链表

数组

排序

原题练习

题目分析

给你若干条已经排好序的链表，要求把它们合并成一条新的升序链表。

一句话概括：

每次从所有链表当前头节点里选最小的那个接到结果链表后面。

接下来怎么看推荐代码：带着这个理解再看推荐代码时，重点观察这条主线：把每条链表当前头节点放进小顶堆，每次弹出最小节点接到结果尾部，再把它的后继压回堆。

结构化讲解

面试时怎么讲

开场思路

这题我会把它看成 k 路归并，用小顶堆维护每条链表当前头节点。

核心过程

先把所有非空链表头放进小顶堆。
每次弹出堆顶最小节点，接到结果链表尾部。
如果这个节点还有后继，就把后继重新压回堆。
直到堆为空，结果链表就完全有序合并好了。

复杂度总结

时间复杂度 O(n log k)，空间复杂度 O(k)。

面试补一句：这题本质上就是“链表版 k 路归并”。

核心思路

合并 K 个有序链表的关键是不要每次都线性比较 K 个头节点。小顶堆能让“当前最小值是谁”始终在 log k 时间内确定下来。

步骤讲解

先把每条链表头节点放进小顶堆

遍历所有链表，把非空头节点加入按节点值排序的小顶堆。

为什么这样做：这些头节点就是当前所有候选最小值的来源。

对应代码提示：PriorityQueue heap = new PriorityQueue<>((a, b) -> a.val - b.val);

每次弹出当前最小节点接到答案尾部

堆顶节点一定是所有未处理节点里最小的，把它接到结果链表末尾。

为什么这样做：这样构造出的结果链表天然保持全局有序。

对应代码提示：ListNode node = heap.poll(); tail.next = node; tail = tail.next;

把弹出节点的后继重新放回堆

如果当前最小节点还有后继，就把它所在链表的下一个节点继续压入堆。

为什么这样做：每条链表的候选头会随着弹出操作不断向后推进。

对应代码提示：if (node.next != null) heap.offer(node.next);

易错点

每轮手动扫 k 个头节点

虽然能做，但会把复杂度拉到 O(nk)，当 k 大时明显变慢。

正确理解：用小顶堆统一维护当前 k 路候选头。

堆里压入空节点

会导致比较器或弹出逻辑出错。

正确理解：初始化和更新时都只压非空节点。

接入结果后忘记推进 tail

后续节点会覆盖已有连接，结果链表结构错误。

正确理解：每次接入新节点后都同步更新 tail。

复杂度与适用判断

时间复杂度：O(n log k)

空间复杂度：O(k)

比其他方案更好在哪里：比顺序两两合并更稳，尤其当链表数量很多时优势更明显。

适用判断：多路有序流合并时，优先考虑小顶堆或分治归并。

额外提醒

堆里保留的不是所有节点，而是每条链表当前最前面的候选节点。

其他语言 / 其他解法

分治算法

分治法：将k个链表分成两组，分别合并，然后再合并结果。时间复杂度为O(n*logk)，其中k是链表数量，n是所有链表的节点总数。空间复杂度为O(logk)，主要用于递归调用栈。

时间复杂度：O(n*logk)

空间复杂度：O(logk)

一句话思路：分治法：将k个链表分成两组，分别合并，然后再合并结果。时间复杂度为O(n*logk)，其中k是链表数量，n是所有链表的节点总数。空间复杂度为O(logk)，主要用于递归调用栈。

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }
}

迭代法

迭代法：依次合并两个链表，直到所有链表合并完成。时间复杂度为O(k*n)，其中k是链表数量，n是所有链表的节点总数。空间复杂度为O(1)，只使用了常数级别的额外空间。

时间复杂度：O(k*n)

空间复杂度：O(1)

一句话思路：迭代法：依次合并两个链表，直到所有链表合并完成。时间复杂度为O(k*n)，其中k是链表数量，n是所有链表的节点总数。空间复杂度为O(1)，只使用了常数级别的额外空间。

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for (int i = 0; i < lists.length; ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }
}

动画演示

如果你还没完全看懂，可以展开动画演示。

优先队列动画演示

想看这段解法是怎么一步步运行的，可以展开动画继续观察。

链表值（每行一个链表，用逗号分隔）

准备就绪 - 输入链表值（用逗号分隔），然后点击开始

分治算法动画演示

想看这段解法是怎么一步步运行的，可以展开动画继续观察。

链表值（每行一个链表，用逗号分隔）

准备就绪 - 输入链表值（用逗号分隔），然后点击开始

迭代法动画演示

想看这段解法是怎么一步步运行的，可以展开动画继续观察。

链表值（每行一个链表，用逗号分隔）

准备就绪 - 输入链表值（用逗号分隔），然后点击开始

动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。