Merge k sorted lists

Hard TimeO(n log k) SpaceO(1)

Given lists, an array of k linked lists that are each already sorted ascending, merge them all into a single sorted list and return its head. Some of the lists may be empty, and the result holds every node from every input.

Examples

Example 1

Input
node = mergeKLists([buildList([1, 5, 9]), buildList([2, 6]), buildList([3, 7]), buildList([4, 8])])
Output
[1,2,3,4,5,6,7,8,9]
Four sorted lists, nine values, one ascending run.

Example 2

Input
node = mergeKLists([buildList([1, 4]), buildList([]), buildList([2, 3])])
Output
[1,2,3,4]
The empty list contributes nothing, and the other four values come back in order.

The Code

function buildList(values) {
  let head = null;
  for (let i = values.length - 1; i >= 0; i--) {
    head = { val: values[i], next: head };
  }
  return head;
}
function toArray(node) {
  const out = [];
  while (node) {
    out.push(node.val);
    node = node.next;
  }
  return out;
}
function mergeTwo(a, b) {
  const dummy = { val: 0, next: null };
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) {
      tail.next = a;
      a = a.next;
    } else {
      tail.next = b;
      b = b.next;
    }
    tail = tail.next;
  }
  tail.next = a ? a : b;
  return dummy.next;
}
function mergeKLists(lists) {
  if (lists.length === 0) return null;
  let step = 1;
  while (step < lists.length) {
    for (let i = 0; i + step < lists.length; i += step * 2) {
      lists[i] = mergeTwo(lists[i], lists[i + step]);
    }
    step = step * 2;
  }
  return lists[0];
}
toArray(mergeKLists([buildList([1, 5, 9]), buildList([2, 6]), buildList([3, 7]), buildList([4, 8])]));
Done

The first 16 calls, of 58. This one does not fit on a page.

Step through toArray(mergeKLists([buildList([1, 5, 9]), buildList([2, 6]), buildList([3, 7]), buildList([4, 8])])) call by call

More like this

All linked lists examples (9) →