#21 Merge Two Sorted Lists

Problem Statement

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list by splicing together the nodes.

Intuition

Since both lists are already sorted, we only need to compare the current heads and always pick the smaller one. This naturally lends itself to a recursive or iterative approach.

Approach

1. Use a dummy head node to simplify edge cases.
2. Compare the heads of both lists.
3. Attach the smaller node to the result and advance that list's pointer.
4. When one list is exhausted, attach the remainder of the other.

Solution

function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null
): ListNode | null {
  if (!list1) return list2;
  if (!list2) return list1;

  if (list1.val <= list2.val) {
    list1.next = mergeTwoLists(list1.next, list2);
    return list1;
  } else {
    list2.next = mergeTwoLists(list1, list2.next);
    return list2;
  }
}

Complexity Analysis