合并 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 =
输出：[]

思路&js代码

1、两两合并，顺序合并

var mergeTwoLists = function (l1, l2) {
  if (l1 === null) {
    return l2
  } else if (l2 === null) {
    return l1
  } else if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2)
    return l1
  } else {
    l2.next = mergeTwoLists(l1, l2.next)
    return l2
  }
}
 
var mergeKLists = function (lists) {
  const m = lists.length
  if (m === 0) {
    return null
  }
  let result = lists[0]
  for (let i = 1; i < lists.length; i++) {
    result = mergeTwoLists(lists[i], result)
  }
  return result
}

2、两两合并，分治合并

var mergeTwoLists = function (l1, l2) {
  if (l1 === null) {
    return l2
  } else if (l2 === null) {
    return l1
  } else if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2)
    return l1
  } else {
    l2.next = mergeTwoLists(l1, l2.next)
    return l2
  }
}
 
var mergeKLists = function (lists) {
  // 合并从 lists[i] 到 lists[j-1] 的链表
  function merge(i, j) {
    const m = j - i
    if (m === 0) {
      return null // 注意输入的 lists 可能是空的
    }
    if (m === 1) {
      return lists[i] // 无需合并，直接返回
    }
    const left = merge(i, i + (m >> 1)) // 合并左半部分
    const right = merge(i + (m >> 1), j) // 合并右半部分
    return mergeTwoLists(left, right) // 最后把左半和右半合并
  }
  return merge(0, lists.length)
}