合并k个升序链表

Tips

题目类型: 链表, 合并链表, 分治

相关题目:

• 21. 合并两个有序链表

题目

将多个链表合并成一个, 并保证新生成的链表按从小到大排序.

提示:

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

示例

输入: [1 -> 4 -> 5, 1 -> 3 -> 4, 2 -> 6]

输出: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

题解

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
  if (!lists || lists.length === 0) {
    return null
  }

  // 引入递归函数 merge, 处理 lists[start] 到 lists[end] 范围内的合并
  const merge = (start, end) => {
    // 1. 基本情况 (Base Case)
    // 当范围缩小到只有一个链表时, 直接返回该链表
    if (start === end) {
      return lists[start]
    }

    // 2. 分解 (Divide)
    const mid = Math.floor((start + end) / 2)

    // 递归合并左半部分
    const left = merge(start, mid)

    // 递归合并右半部分
    const right = merge(mid + 1, end)

    // 3. 合并 (Conquer)
    // 将左右两部分的结果使用 mergeTwoLists 函数进行合并
    return mergeTwoLists(left, right)
  }

  // 从整个链表数组的范围 [0, lists.length - 1] 开始递归
  return merge(0, lists.length - 1)
}

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
// 这个就是 21 题原题
var mergeTwoLists = function (l1, l2) {
  const dummy = new ListNode(-1)
  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
  }

  if (!l1) curr.next = l1
  if (!l2) curr.next = l2

  return dummy.next
}