21. Merge Two Sorted Lists

Merge two sorted linked lists into one sorted list by splicing their nodes together. Return the merged head.

The smaller head goes first; its next is the merge of the remaining nodes.

1function mergeTwoLists(a: ListNode | null, b: ListNode | null): ListNode | null {
2  if (!a) return b;
3  if (!b) return a;
4  if (a.val <= b.val) { a.next = mergeTwoLists(a.next, b); return a; }
5  b.next = mergeTwoLists(a, b.next);
6  return b;
7}

list1 (from a)

→

→ ∅

list2 (from b)

→

→ ∅

call stack

1 → merge(…)

1 ≤ 1: 1 goes first.

1 / 0

Space: play/pause · ←/→: step