1.暴力遍历求解

  • 遍历所有链表，将节点放到数组当中
  • 根据节点值的大小将数组按顺序排列
  • 用遍历后的数组创建一个新的有序链表

代码如下:

  1. /**
  2.  * Definition for singly-linked list.
  3.  * function ListNode(val) {
  4.  *     this.val = val;
  5.  *     this.next = null;
  6.  * }
  7.  */
  8. /**
  9.  * @param {ListNode[]} lists
  10.  * @return {ListNode}
  11.  */
  12. var mergeKLists = function(lists) {
  13.     let len  = lists.length;
  14.     if(len == 0) return null;
  15.     if(len == 1) return lists[0];
  16.     let arr = new Array();
  17.     for(let i = 0;i<len;i++){
  18.         let temp = lists[i];
  19.         while(temp){
  20.             arr.push(temp.val);
  21.             temp = temp.next;
  22.         }
  23.     }
  24.       //sort在v8下 数组小于10时为插入排序，大于10为快排
  25.     arr.sort((a,b)=>a-b);
  26.     let heap = new ListNode();
  27.     let cur = heap;
  28.     for(let i = 0,len = arr.length;i<len;i++){
  29.         let node = new ListNode(arr[i]);
  30.         cur.next = node;
  31.         cur = cur.next;
  32.     }
  33.     return heap.next;
  34. };

时间复杂度:

  • 遍历所有的节点为O(n)
  • 这里不考虑数组小于10的情况，v8下数组大于10sort为快排, 则O(nlogn)
  • 最后遍历数组转化为列表为O(n)

所以时间复杂度为 O(nlogn) 最坏情况下sort为 O（n）

空间复杂度:**

  • 排序花费O(n) 的空间
  • 创建链表使用O(n)的空间

所以空间复杂度为O(n)
**

2.顺序合并

  • 依次按顺序合并链表
  • 最后将合并出来的链表返回
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
const mergeTwoList = function (l1, l2) {
    if (l2 === null) return l1
    if (l1 === null) return l2
    let p = head = new ListNode()
    let a = l1, b = l2
    while (a && b) {
        if (a.val > b.val) {
            p.next = b
            b = b.next
        } else {
            p.next = a
            a = a.next
        }
        p = p.next
    }
    p.next = a ? a : b
    return head.next
}

var mergeKLists = function (lists) {
    let ans 
    for (let i = 0; i < lists.length; i++) {
        temp = mergeTwoList(temp, lists[i])
    }
    return ans ? ans : null
};

时间复杂度:

  • 假设每个链表的最长长度是 n。在第一次合并后，ans 的长度为 n
  • 第二次合并之后ans长度为2n
  • 第 i 次合并的时间为 O(n+ (i-1) n) ，求和后 总的时间代价为 O(kn)

所以时间复杂度为O(kn)

空间复杂度

  • 没有用到别的数据结构所以为 O(1)

**

3.分治合并（自上而下）

  • 将k个链表两两分组然后合并
  • 每轮合并后剩余的链表数量为 k/2 k/4 k/8 …
  • 将最后合并出来的链表返回
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */

var mergeKLists = function (lists) {
  const _merge = function (lists, start, end) {
    if (end - start < 0) return null
    if (end - start === 0) return lists[end]
    const mid = Math.floor(start + (end - start) / 2)
    return mergeTwoList(_merge(lists, start, mid), _merge(lists, mid + 1, end))
  }

  return _merge(lists, 0, lists.length - 1)
}

const mergeTwoList = function (l1, l2) {
  if (!l1) return l2
  if (!l2) return l1
  let a = l1,
    b = l2
  const head = (p = new ListNode())
  while (a && b) {
    if (a.val > b.val) {
      p.next = b
      b = b.next
    } else {
      p.next = a
      a = a.next
    }
    p = p.next
  }
  if (a) p.next = a
  else p.next = b
  return head.next
}

时间复杂度

  • mergeTwoList合并两个链表的时间复杂度为O(n+m) 这里为O(n)
  • 归并排序的时间复杂度为O(klogk)
  • 次数X操作的复杂度可得最终复杂度为O(kn x logk)

可得时间复杂度为 O(kn x logk)

空间复杂度**

  • 空间复杂度：递归会使用到 O(logk) 空间代价的栈空间。