23. 合并 K 个升序链表

题目描述

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

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

示例 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 = [[]]

输出：[]

提示：

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

出处：LeetCode

解法一：顺序合并

思路

我们可以遍历链表数组，依次合并两个链表，直到合并到最后一个链表。

实现

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  let res: ListNode | null = null;

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

  return res;
}

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  if (l1 === null) {
    return l2;
  }

  if (l2 === null) {
    return l1;
  }

  if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  }
}

复杂度分析

• 时间复杂度：$O(N \log N)$，其中 $N$ 是所有链表的节点总数。合并两个链表的时间复杂度是 $O(N)$，共有 $N$ 个节点。
• 空间复杂度：$O(1)$

解法二：分治合并

思路

我们可以使用分治的方法来合并链表数组。我们将链表数组分为两部分，分别合并两部分链表，然后合并两部分的结果。

实现

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  return merge(lists, 0, lists.length - 1);
}

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

  if (left > right) {
    return null;
  }

  const mid = left + Math.floor((right - left) / 2);
  const l1 = merge(lists, left, mid);
  const l2 = merge(lists, mid + 1, right);

  return mergeTwoLists(l1, l2);
}

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  if (l1 === null) {
    return l2;
  }

  if (l2 === null) {
    return l1;
  }

  if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  }
}

复杂度分析

• 时间复杂度：$O(N \log K)$，其中 $N$ 是所有链表的节点总数，$K$ 是链表数组的长度。
• 空间复杂度：$O(\log K)$，递归调用的栈空间为 $O(\log K)$。

解法三：优先队列

TODO