3.2 Dummy Node Technique

Demo: Merge Two Sorted Lists — LC 21 (Easy — Amazon/Meta/Google High)

Statement (Demo): Given the heads of two sorted linked lists list1 and list2, merge them into one sorted list and return its head. Example: list1=[1,2,4], list2=[1,3,4] → [1,1,2,3,4,4] | ⚡ n,m ≤ 50

Approach: Walk a tail from the dummy; attach the smaller node of the two lists each time. When one list runs out, attach the rest of the other directly.

function mergeTwoLists(a, b) {
  const dummy = { 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 || b;
  return dummy.next;
}

Complexity: Time O(m+n), Space O(1)