23. Merge k Sorted Lists

Problem

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Solution 1

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
  var res = [];
  var tmp = null;
  for (var i = 0; i < lists.length; i++) {
    tmp = lists[i];
    while (tmp !== null) {
      res.push(tmp);
      tmp = tmp.next;
    }
  }
  res.sort((a, b) => (a.val - b.val));
  for (var j = 0; j < res.length; j++) {
    res[j].next = res[j + 1] || null;
  }
  return res[0] || null;
};

Explain:

全部拿出来，再排序。

Complexity:

• Time complexity : O(nlog(n)). n 是节点总数。
• Space complexity : O(n).

Solution 2

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
  var head = new ListNode(0);
  var now = head;
  var i = 0;
  var index = 0;
  var min = null;
  var len = lists.length;
  while (true) {
    min = null;
    for (i = 0; i < len; i++) {
      if (lists[i] && (!min || lists[i].val < min.val)) {
        min = lists[i];
        index = i;
      }
    }
    if (min) {
      now.next = min;
      now = now.next;
      lists[index] = lists[index].next;
    } else {
      break;
    }
  }
  return head.next;
};

Explain:

依次找到目前最小的那个。

Complexity:

• Time complexity : O(n*k). n 是节点总数，k 是链表数量。
• Space complexity : O(1).

Solution 3

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
  var res = null;
  for (var i = 0; i < lists.length; i++) {
    res = merge(res, lists[i]);
  }
  return res;
};

var merge = function (a, b) {
  if (!a) return b;
  if (!b) return a;

  var head = new ListNode(0);
  var now = head;

  while (a || b) {
    if (!a || (b && b.val < a.val)) {
      now.next = b;
      b = b.next;
    } else {
      now.next = a;
      a = a.next;
    }
    now = now.next;
  }

  return head.next;
};

Explain:

链表依次合并。

Complexity:

• Time complexity : O(n*k). n 是节点总数，k 是链表数量。
• Space complexity : O(1).

Solution 4

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
  var len = lists.length;
  var half = Math.ceil(len / 2);
  var i = 0;
  while (len > 1) {
    while (i < half) {
      lists[i] = merge(lists[i * 2], (i * 2 + 1) < len ? lists[i * 2 + 1] : null);
      i++;
    }
    len = half;
    half = Math.ceil(len / 2);
    i = 0;
  }
  return lists[0] || null;
};

var merge = function (a, b) {
  if (!a) return b;
  if (!b) return a;
  if (a === b) return a;

  var head = new ListNode(0);
  var now = head;

  while (a || b) {
    if (!a || (b && b.val < a.val)) {
      now.next = b;
      b = b.next;
    } else {
      now.next = a;
      a = a.next;
    }
    now = now.next;
  }

  return head.next;
};

Explain:

链表二分合并。

Complexity:

• Time complexity : O(nlog(k)). n 是节点总数，k 是链表数量。
• Space complexity : O(1).