合并 K 个升序链表

题目描述

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

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

示例

输入：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

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

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

约束条件

• k == lists.length
• 0 <= k <= 10⁴
• 0 <= lists[i].length <= 500
• -10⁴ <= lists[i][j] <= 10⁴
• lists[i] 按升序排列
• lists[i].length 的总和不超过 10⁴

我的解题过程

第一次尝试：顺序合并

一开始想到的思路是复用「合并两个有序链表」的方法。既然我已经会合并两个链表了，那合并 K 个链表不就是把它们一个一个合并起来吗？

具体来说就是：

• 先写一个合并两个链表的辅助函数 computed
• 用一个变量 res 保存当前合并的结果
• 遍历链表数组，每次把 res 和下一个链表合并

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  const computed = (l1: ListNode | null, l2: ListNode | null): ListNode | null => {
    let head = new ListNode(0);
    let tail = head;

    while (l1 && l2) {
      if (l1.val < l2.val) {
        tail.next = l1;
        l1 = l1.next;
      } else {
        tail.next = l2;
        l2 = l2.next;
      }
      tail = tail.next;
    }

    tail.next = l1 || l2;
    return head.next;
  };

  let res: ListNode | null = null;

  for (let i = 0; i < lists.length; i++) {
    res = computed(res, lists[i]);
  }

  return res;
}

这个方法的时间复杂度是 O(k²n)，其中 k 是链表数量，n 是平均链表长度。因为每次合并后链表会变长，后面的合并会越来越慢。

优化思路：分治合并

可以用分治的思想来优化。把 k 个链表分成两半，分别合并，最后再把两个结果合并。这样时间复杂度可以优化到 O(kn log k)。

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  const mergeTwoLists = (l1: ListNode | null, l2: ListNode | null): ListNode | null => {
    let head = new ListNode(0);
    let tail = head;

    while (l1 && l2) {
      if (l1.val < l2.val) {
        tail.next = l1;
        l1 = l1.next;
      } else {
        tail.next = l2;
        l2 = l2.next;
      }
      tail = tail.next;
    }

    tail.next = l1 || l2;
    return head.next;
  };

  const merge = (lists: Array<ListNode | null>, left: number, right: number): ListNode | null => {
    if (left > right) return null;
    if (left === right) return lists[left];

    const mid = Math.floor((left + right) / 2);
    return mergeTwoLists(merge(lists, left, mid), merge(lists, mid + 1, right));
  };

  return merge(lists, 0, lists.length - 1);
}

小结

这道题有多种解法：

1. 顺序合并：最直观，时间复杂度 O(k²n)
2. 分治合并：用分治思想优化，时间复杂度 O(kn log k)
3. 优先队列（堆）：维护一个大小为 k 的最小堆，每次取出最小的节点，时间复杂度 O(kn log k)

这道题的核心是把问题分解成更小的子问题（合并两个链表），然后考虑如何高效地组合这些子问题的解。分治的思想在很多场景下都能大幅优化算法效率。