Merge Two Sorted Lists0/59 done
Part 2 · Problems · Linked list

Merge Two Sorted Lists

#21 · Easy · LeetCode

Merge two sorted linked lists into one sorted list.

1->2->4 + 1->3->4 -> 1->1->2->3->4->4

Ask before coding

Hint

A dummy head means you never special-case the first node.

Approach

Dummy node plus tail. Attach the smaller head, advance it. When one list ends, attach the rest of the other.

Time O(m + n)   Space O(1)

Watch it run
Solution (JavaScript, tested)
function mergeTwoLists(a, b) {
  const dummy = new ListNode(0);
  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 ?? b;
  return dummy.next;
}

Traps

Say out loud: Dummy head so the first node isn't a special case, then a standard merge.