合并K个升序链表

题目

题目来源：力扣（LeetCode）

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 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 个链表配对并将同一对中的链表合并；
• 第一轮合并以后， k 个链表被合并成了 (k/2) 个链表，平均长度为 (2n)/k ，然后是 k/4个链表，k/8 个链表等等；
• 重复这一过程，直到我们得到了最终的有序链表。

/**
 * 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) {
  return merge(lists, 0, lists.length - 1)
};
const merge = (lists, l, r) => {
  if (l == r) {
    return lists[l]
  }
  if (l > r) {
    return null
  }
  // 右移动1位就是除以2；计算中间数的位置
  const mid = (l + r) >> 1;
  return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r))
}
/**
  @description 合并两个有序链表
  @param {ListNode} head1 链表1 的头节点
  @param {ListNode} head2 链表2 的头节点
  @return {}
 */
const mergeTwoLists = (head1, head2) => {
  if (head1 == null || head2 == null) {
    return head1 != null ? head1 : head2;
  }
  // 创建一个虚拟头节点来保存合并之后链表的头部
  const dummyHead = new ListNode(0)
  // tail 指针用来记录下一个插入位置的前一个位置
  // aPtr 指针用来记录链表1未合并部分的第一位
  // bPtr 指针用来记录链表2未合并部分的第一位
  let tail = dummyHead, aPtr = head1, bPtr = head2;
  while (aPtr != null && bPtr != null) {
    if (aPtr.val < bPtr.val) {
      tail.next = aPtr;
      aPtr = aPtr.next
    } else {
      tail.next = bPtr;
      bPtr = bPtr.next
    }
    tail = tail.next;
  }
  // 比较哪个链表还有没被比较完的值，直接把temp指针指向他
  tail.next = aPtr != null ? aPtr : bPtr;
  // 返回排序好的链表头
  return dummyHead.next;
}