23. 合并K个升序链表#

生活中的多路合并#

想象你是一个大学食堂的管理员。食堂有k个打饭窗口，每个窗口前都排着一队按身高从矮到高的学生（就像我们的有序链表）。你的任务是将所有学生重新排成一个队，依然要保持按身高从矮到高的顺序。这就是我们今天要讨论的合并k个升序链表问题的生动写照。

问题描述#

题目目标#

给你一个链表数组，每个链表都已经按升序排列。请将所有链表合并到一个升序链表中，并返回合并后的链表头节点。

示例 1#

输入： lists = [[1,4,5],[1,3,4],[2,6]] 输出： [1,1,2,3,4,4,5,6] 说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。

补充说明#

链表题的输入本质上是节点之间的连接关系，重点通常是返回处理后的头节点或目标节点。

问题的本质与挑战#

LeetCode第23题”合并K个升序链表”要求我们将K个有序链表合并成一个新的有序链表。这个问题乍看简单，实则暗藏玄机：如何在保证结果有序的同时，又能达到最优的时间复杂度？

例如：

输入：
[
  1→4→5,
  1→3→4,
  2→6
]
输出：1→1→2→3→4→4→5→6

plaintext

解题思路的进化#

方法一：逐个合并法#

就像食堂管理员最直观的想法：先合并前两队，再把结果和第三队合并，以此类推。这种方法简单但效率不高，因为前面的元素会被重复比较多次。

方法二：分治合并法#

更聪明的方式是采用分治思想：先把k个队伍分成两半，各自合并后再合并到一起。就像举办体育比赛的淘汰赛制一样，这样可以显著减少比较次数。

方法三：优先队列法#

最优雅的解法是利用优先队列：每个打饭窗口派出当前队伍的第一个学生到一个中心区域（优先队列），始终从中选出最矮的学生，然后该学生所在的窗口再派出下一个学生。这样我们可以始终保证选出的是当前最小的元素。

详细代码实现#

让我们先来看最优雅的优先队列解法：

public ListNode mergeKLists(ListNode[] lists) {
    // 边界处理：数组为空或长度为0时，没有可合并链表
    if (lists == null || lists.length == 0) return null;

    // pq：最小堆（优先队列），堆顶始终是当前所有候选节点中的最小值
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);

    // 把每条链表的头节点放入堆，作为初始候选集合
    for (ListNode node : lists) {
        if (node != null) {
            pq.offer(node);
        }
    }

    // dummy：结果链表哨兵节点
    ListNode dummy = new ListNode(0);
    // tail：结果链表尾指针，负责持续尾插
    ListNode tail = dummy;

    // 循环直到堆为空：每次取最小节点接到结果后面
    while (!pq.isEmpty()) {
        // curr：当前最小节点（弹出堆顶）
        ListNode curr = pq.poll();
        // 连接到结果链表尾部
        tail.next = curr;
        // 结果尾指针后移
        tail = tail.next;

        // 若该节点所在链表还有后继，则把后继加入堆参与后续比较
        if (curr.next != null) {
            pq.offer(curr.next);
        }
    }

    // 返回真实头节点（跳过哨兵）
    return dummy.next;
}

java

再来看分治合并法的实现：

public ListNode mergeKLists(ListNode[] lists) {
    // 边界处理：空输入直接返回 null
    if (lists == null || lists.length == 0) return null;
    // 分治合并区间 [0, lists.length - 1]
    return mergeSort(lists, 0, lists.length - 1);
}

private ListNode mergeSort(ListNode[] lists, int left, int right) {
    // 递归终止：区间内只剩一个链表，天然有序，直接返回
    if (left == right) return lists[left];

    // 计算中点，把问题拆为左右两半
    int mid = left + (right - left) / 2;
    // 递归合并左半部分
    ListNode leftList = mergeSort(lists, left, mid);
    // 递归合并右半部分
    ListNode rightList = mergeSort(lists, mid + 1, right);

    // 把两条有序链表再合并成一条有序链表
    return mergeTwoLists(leftList, rightList);
}

private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // dummy：哨兵节点，简化结果链表头处理
    ListNode dummy = new ListNode(0);
    // tail：结果链表当前尾节点
    ListNode tail = dummy;

    // 双指针比较并依次挂接较小节点
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        // 尾指针后移
        tail = tail.next;
    }

    // 拼接剩余链表（最多一个非空）
    tail.next = (l1 != null) ? l1 : l2;
    // 返回真实头节点
    return dummy.next;
}

java

复杂度分析与比较#

优先队列法：

时间复杂度：O(N logK)，N是所有节点总数，K是链表个数
空间复杂度：O(K)，优先队列中最多K个节点
优点：实现优雅，处理过程清晰
缺点：需要额外的数据结构

分治合并法：

时间复杂度：O(N logK)
空间复杂度：O(logK)，递归调用栈的深度
优点：不需要额外的数据结构
缺点：实现稍复杂，递归调用有开销

逐个合并法：

时间复杂度：O(NK)
空间复杂度：O(1)
优点：实现最简单
缺点：效率较低，重复比较次数多

实战技巧总结#

优先队列的初始化技巧：把Lambda表达式用于比较器定义使代码更简洁
虚拟头节点的使用：简化边界情况的处理
分治时计算中点：使用 left + (right - left) / 2 避免整数溢出
合并过程的细节：注意指针更新的顺序，防止断链

应用场景延伸#

K路归并的思想在实际开发中非常常见：

多路文件合并
数据库的多路归并
分布式系统的结果聚合
实时数据流的合并排序

小结#

合并K个升序链表的问题教会我们：

如何将简单问题（合并两个有序链表）扩展到复杂场景
不同解法之间的权衡取舍
数据结构（优先队列）在算法优化中的重要作用
分治思想的实际应用

记住：解决复杂问题如同管理食堂打饭，找到合适的策略才能实现最优效率！

补充思考：

如果链表数量K很大，如何优化内存使用？
如果是流式数据，如何调整算法？
如何处理链表长度相差很大的情况？