Merge Two Sorted Lists

Why it belongs on this sheet

This is a clean test of pointer handling and a common stepping stone to harder merge problems.

Pattern

Dummy node merge

Approach

Use a dummy head and keep attaching the smaller front node from either list. When one list ends, attach the remainder of the other list.

Java solution

class Solution {
  public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;

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

    tail.next = list1 != null ? list1 : list2;
    return dummy.next;
  }
}

Complexity

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

Interview note

The dummy node keeps edge cases small and the explanation cleaner.