合并 K 个升序链表

LeetCode 官方题目链接

1. 题目呈现

难度等级：🔴 困难
核心考察点：链表、分治、最小堆 (优先队列)

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

---

2. 解题思路拆解

方法一：分治法 (Merge Sort 思想)

这道题其实是 "合并两个有序链表" 的推广。 我们可以两两合并：

1. 将 lists 中的链表两两配对合并。
2. 合并后，lists 长度减半。
3. 重复上述过程，直到只剩下一个链表。

例如有 4 个链表：L1, L2, L3, L4

• 第一轮：合并 (L1, L2) 得到 M1，合并 (L3, L4) 得到 M2。
• 第二轮：合并 (M1, M2) 得到最终结果。

方法二：最小堆 (优先队列)

维护一个大小为 k (链表条数) 的最小堆。

1. 将每个链表的头节点加入堆。
2. 每次从堆中取出最小的节点（堆顶），接到结果链表后面。
3. 如果这个节点有 next，将其 next 放入堆中。
4. 重复直到堆为空。

JavaScript 没有内置的 PriorityQueue，手写堆比较麻烦，面试中通常允许使用 分治法，因为它的复杂度也是优秀的 $O(N \log k)$。

---

3. 代码实现 (分治法)

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    if (lists.length === 0) return null;
    return merge(lists, 0, lists.length - 1);
};

// 分治合并
function merge(lists, left, right) {
    if (left === right) return lists[left];
    
    const mid = Math.floor((left + right) / 2);
    const l1 = merge(lists, left, mid);
    const l2 = merge(lists, mid + 1, right);
    
    return mergeTwoLists(l1, l2);
}

// 基础函数：合并两个有序链表
function mergeTwoLists(l1, l2) {
    const dummy = new ListNode(0);
    let curr = dummy;
    
    while (l1 && l2) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    
    curr.next = l1 ? l1 : l2;
    return dummy.next;
}

代码执行演示

输入 lists = [L1, L2, L3] (假设 L1=[1], L2=[2], L3=[3])

1. merge(0, 2):
   • mid = 1.
   • Call merge(0, 1) -> returns merged(L1, L2).
   • Call merge(2, 2) -> returns L3.
   • Merge merged(L1, L2) and L3.
2. Inside merge(0, 1):
   • mid = 0.
   • Call merge(0, 0) -> returns L1.
   • Call merge(1, 1) -> returns L2.
   • Merge L1 and L2.

---

4. 复杂度分析

维度	描述
时间复杂度	$O(N \log k)$。$N$ 是所有节点总数，$k$ 是链表条数。分治树的高度是 $\log k$，每一层都需要遍历 $N$ 个节点。
空间复杂度	$O(\log k)$。递归栈的深度。