Merge two sorted lists

Easy TimeO(n + m) SpaceO(1)

Given the heads of two linked lists that are each already sorted ascending, splice them into one sorted list and return its head — [1, 3, 5] and [2, 4, 6] give [1, 2, 3, 4, 5, 6]. The result is built by relinking the existing nodes, not by copying values into a new list, and either list may be empty.

Examples

Example 1

Input
node = mergeTwoLists(buildList([1, 3, 5]), buildList([2, 4, 6]))
Output
[1,2,3,4,5,6]
Six values interleaved into one ascending run.

Example 2

Input
node = mergeTwoLists(buildList([]), buildList([2, 4]))
Output
[2,4]
One side is empty, so the other comes back whole and untouched.

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 mergeTwoLists(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;
}
toArray(mergeTwoLists(buildList([1, 3, 5]), buildList([2, 4, 6])));
Done

The first 9 calls, of 25. This one does not fit on a page.

Step through toArray(mergeTwoLists(buildList([1, 3, 5]), buildList([2, 4, 6]))) call by call

More like this

All linked lists examples (9) →