Merge Two Sorted Lists

Approach Summary

Use a dummy head node. Compare heads of both lists, advance the smaller one. Attach remaining list at the end.

Full Solution & Approach

Use a dummy head to avoid special-casing the first node. Compare the heads of l1 and l2, append the smaller node to the current pointer, advance that list, and move the current pointer forward. Repeat until one list is exhausted, then attach the remainder of the other list in one operation — those remaining nodes are already in sorted order. The dummy node keeps the code uniform because even the first real node is attached to dummy.next rather than handled with an if/else. This runs in O(n + m) time with O(1) space, using only pointer rewiring. The recursive version returns the smaller head and recurses on its next — cleaner to write but uses O(n + m) stack space, so the iterative dummy-head version is usually preferred in interviews.

Each node of both lists is visited once — O(n + m) time. Constant extra pointers — O(1) space.

Solution Code

Solution

def merge_two_lists(l1, l2):
    dummy = cur = ListNode(0)
    while l1 and l2:
        if l1.val <= l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next
    cur.next = l1 or l2
    return dummy.next

function mergeTwoLists(l1, l2) {
  const dummy = new ListNode(0);
  let cur = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) {
      cur.next = l1;
      l1 = l1.next;
    } else {
      cur.next = l2;
      l2 = l2.next;
    }
    cur = cur.next;
  }
  cur.next = l1 || l2;
  return dummy.next;
}

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), cur = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; }
        else { cur.next = l2; l2 = l2.next; }
        cur = cur.next;
    }
    cur.next = l1 != null ? l1 : l2;
    return dummy.next;
}

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    while (l1 && l2) {
        if (l1->val <= l2->val) { cur->next = l1; l1 = l1->next; }
        else { cur->next = l2; l2 = l2->next; }
        cur = cur->next;
    }
    cur->next = l1 ? l1 : l2;
    return dummy.next;
}

Edge Cases to Watch

Both lists empty — return null
One list empty — return the other
One list runs out mid-merge — the tail attach handles it
Duplicate values across lists — the <= comparison keeps the merge correct

How to Recognize This Pattern

Merge two sorted sequences
Dummy head pattern

Complexity Analysis

Time Complexity

O(n + m)

Space Complexity

O(1)