Merge Two Sorted Lists

Examples

Input: list1 = [1, 2, 4], list2 = [1, 3, 4]
Output: [1, 1, 2, 3, 4, 4]

Input: list1 = [], list2 = []
Output: []

Input: list1 = [], list2 = [0]
Output: [0]

Constraints

• The number of nodes in each list is between 0 and 50.

• -100 <= Node.val <= 100

• Both lists are sorted in non-decreasing order.

Approach

One way to think about this: dump every value from both lists into one big collection, sort that collection, then rebuild a list from it. That works, but it throws away the fact that the lists were already sorted — you're paying for a full sort you don't actually need.

Since both lists arrive pre-sorted, you can instead walk them side by side with two pointers. At each step, whichever list currently has the smaller front value gets attached next to the result, and only that pointer advances. Repeating this until one list is exhausted, then tacking on the remainder of the other list, produces the merged list in a single pass.

Solutions

Brute Force — Collect, Sort, Rebuild

Read every value out of both lists into a plain array, sort that array, and build a fresh list from the sorted values. This ignores the fact that each input list was already sorted, so it does more comparison work than necessary.

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function mergeTwoLists(list1, list2) {
  const values = [];

  let node = list1;
  while (node) {
    values.push(node.val);
    node = node.next;
  }
  node = list2;
  while (node) {
    values.push(node.val);
    node = node.next;
  }

  values.sort((a, b) => a - b);

  const dummy = new ListNode(0);
  let curr = dummy;
  for (const value of values) {
    curr.next = new ListNode(value);
    curr = curr.next;
  }

  return dummy.next;
}

Time: O((n + m) log(n + m)) · Space: O(n + m)

Optimal — Two-Pointer Merge

Keep one pointer on each list. Compare their front values, splice the smaller node onto the end of the result, and advance only the pointer that lost the comparison. A dummy node at the front of the result gives you a stable place to hang the very first real node without any special casing. When one list runs dry, the remainder of the other list is already sorted, so it can be attached in one step.

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function mergeTwoLists(list1, list2) {
  const dummy = new ListNode(0);
  let curr = dummy;

  while (list1 !== null && list2 !== null) {
    if (list1.val <= list2.val) {
      curr.next = list1;
      list1 = list1.next;
    } else {
      curr.next = list2;
      list2 = list2.next;
    }
    curr = curr.next;
  }

  // At most one of these still has nodes left, and they're already sorted.
  curr.next = list1 !== null ? list1 : list2;

  return dummy.next;
}

Time: O(n + m) · Space: O(1) — reuses existing nodes