Blind 75Easy

Merge Two Sorted Lists — Dummy Head Merge

Use a dummy head and advance two pointers, always stitching the smaller node into the merged list.

Linked ListTwo Pointers

View problem on LeetCode

Problem Statement

Merge two sorted singly linked lists into a single sorted list.

Why This Problem Matters

Teaches in-place merging without extra arrays or allocations.
Forms the basis of linked-list merge sort and k-way merges.
Highlights dummy nodes as a pattern for simplifying head handling.

Thought Process

Compare heads iteratively

Always append the smaller head node to the merged list.

Keep pointers moving

Advance whichever list contributed a node to maintain sorted order.

Attach the remaining tail

Once one list finishes, append the leftover nodes from the other list.

Step-by-Step Reasoning

Initialise a dummy node and a current pointer.
While both lists are non-null, pick the smaller node and append it to current.
Advance current and whichever list provided the node.
Attach the non-null list after the loop and return dummy.next.

Dry Run

l1 = 1→2→4, l2 = 1→3→4

Merged list grows as 1→1→2→3→4→4.

l1 empty

Loop skipped, result is l2.

Complexity Analysis

Time

O(n + m)

Space

O(1)

Why

Each node is visited once and we reuse existing nodes.

Annotated Solution

JAVA

public class MergeTwoSortedLists {
  public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode();
    ListNode tail = dummy;

    ListNode a = l1;
    ListNode b = l2;

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

    tail.next = (a != null) ? a : b;
    return dummy.next;
  }

  public static class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) {
      this.val = val;
      this.next = next;
    }
  }
}

Iteratively picking the smaller node preserves sorted order while the dummy head simplifies list construction.

Common Pitfalls

Forgetting to update current.next after reassigning leaves cycles.
Not handling empty lists can throw NullPointerException.
Returning dummy instead of dummy.next leaves the extra head in place.

Follow-Up Questions

How would you solve this recursively and what is the stack cost?
Can you merge lists stored as arrays using a similar approach?

Key Takeaways

Dummy heads eliminate edge cases for linked-list merges.

Always update traversal pointers immediately after rewiring.

This merge routine is the core of linked-list merge sort.