描述

合并K个升序的链表并将结果作为一个升序链表返回其头结点。

示例

输入：[{1,2,3},{4,5,6,7}]
返回值：{1,2,3,4,5,6,7}

输入：[{1,2},{3,4,5},{6}]
返回值：{1,2,3,4,5,6}

题解

前置知识：合并两个有序链表

在解决「合并K个排序链表」这个问题之前，我们先来看一个更简单的问题：如何合并两个有序链表？假设链表 a 和 b 的长度都是 n，如何在 O(n) 的时间代价以及 O(1) 的空间代价完成合并？

这个问题在面试中常常出现，为了达到空间代价是 O(1)，我们的宗旨是「原地调整链表元素的 next 指针完成合并」。以下是合并的步骤和注意事项。

• 首先我们需要一个变量 head 来保存合并之后链表的头部，你可以把 head 设置为一个虚拟的头（也就是 head 的 val 属性不保存任何值），这是为了方便代码的书写，在整个链表合并完之后，返回它的下一位置即可。
• 我们需要一个指针 tail 来记录下一个插入位置的前一个位置，以及两个指针 aPtr 和 bPtr 来记录 a 和 b 未合并部分的第一位。注意这里的描述，tail 不是下一个插入的位置，aPtr 和 bPtr 所指向的元素处于「待合并」的状态，也就是说它们还没有合并入最终的链表。 当然你也可以给他们赋予其他的定义，但是定义不同实现就会不同。
• 当 aPtr 和 bPtr 都不为空的时候，取 val 熟悉较小的合并；如果 aPtr 为空，则把整个 bPtr 以及后面的元素全部合并；bPtr 为空时同理。
• 在合并的时候，应该先调整 tail 的 next 属性，再后移 tail 和 *Ptr（aPtr 或者 bPtr）。那么这里 tail 和 *Ptr 是否存在先后顺序呢？它们谁先动谁后动都是一样的，不会改变任何元素的 next 指针。

// 构造函数
function ListNode(x){
  this.val = x;
  this.next = null;
}
function mergeTwoList(pHead1, pHead2) {
  // 创建一个虚拟头节点 在最后新的链表 生成之后，需要借助这个指针来移动
  let dummy = new ListNode(-1)
  // 将当前的指针赋值给 cur 变量，真正移动的是它
  let cur = dummy  
  // 循环的条件是 两个链表的全部不为空
  // 针对为空的部分在最后单独处理
  while(pHead1 !== null && pHead2 !== null) {
    if(pHead1.val < pHead2.val) {
      cur.next = pHead1
      pHead1 = pHead1.next
    } else {
      cur.next = pHead2
      pHead2 = pHead2.next
    }
    // 当前移动指针
    cur = cur.next
  }
  // 处理长度不等的情况，将剩余的部分放在最后
  cur.next = pHead1 || pHead2
  // 返回新链表的头节点
  return dummy.next
}
module.exports = {
  mergeTwoList : mergeTwoList
};

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

顺序合并

我们可以想到一种最朴素的方法：用一个变量 ans 来维护以及合并的链表，第 i 次循环把第 i 个链表和 ans 合并，答案保存到 ans 中。

/**
 * 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}
 */
// 给的一种思路是使用for循环处理这个问题
var mergeKLists = function (lists) {
  let ans = null;
  for (let k = 0; k < lists.length; k++) {
    ans = mergeTwoList(ans,lists[k])
  }
  return ans;
};