Free lesson · DSA Mastery - Interview Prep, End to End

Merge Two Sorted Lists

Medium7 min readdsarecursion-backtracking

Merge Two Sorted Lists

Merge Two Sorted Lists is the gentlest possible introduction to recursion: combine two sorted linked lists into one sorted list. There's no branching and no backtracking yet - it's a clean warm-up that shows how a recursive function expresses "do a little work, then delegate the rest to a smaller version of yourself." The recursive insight is elegant: the merged list's head is the smaller of the two input heads, and the rest of the merged list is just the merge of what remains. We present the iterative two-pointer approach and the recursive approach side by side, because seeing the same problem solved both ways is the best way to build recursive intuition.

The insight: merge(a, b) = take the smaller head, then attach merge(restOfThatList, otherList). Each call resolves one node and hands off a strictly smaller problem, so the recursion terminates when either list empties.

The Problem

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input:  list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input:  list1 = [], list2 = []
Output: []

Example 3:

Input:  list1 = [], list2 = [0]
Output: [0]

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

Approaches Overview

Both run in linear time. The iterative version uses constant extra space; the recursive version uses stack space proportional to the total length but reads as a near-direct translation of the problem's definition - ideal for learning the recursive mindset.

Approach 1: Iterative with Dummy Head

The Idea

Use a dummy node to anchor the result and a tail pointer to append to. Walk both lists; attach the smaller current node to tail, advance that list, and move tail forward. When one list empties, attach the remainder of the other. The dummy removes the special case of choosing the very first node.

Logic Flowchart

graph TD
    A["dummy; tail = dummy"] --> B{"both lists non-empty?"}
    B -->|No| C["attach remaining list to tail"]
    B -->|Yes| D{"list1.val <= list2.val?"}
    D -->|Yes| E["tail.next = list1; list1 = list1.next"]
    D -->|No| F["tail.next = list2; list2 = list2.next"]
    E --> G["tail = tail.next"]
    F --> G
    G --> B
    C --> H["return dummy.next"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the iterative merge. A dummy head anchors the result and a tail pointer appends the smaller current node, advancing that list each time. When one list empties, the remainder of the other is attached.

Code

public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(0), 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;     // attach the remainder
    return dummy.next;
}

// ListNode: int val; ListNode next;
// Usage: mergeTwoLists([1,2,4],[1,3,4]) -> [1,1,2,3,4,4]

This Java code merges iteratively using a dummy head and a tail pointer. It attaches the smaller current node each step, advances that list, and finally splices on whatever remains of the non-empty list.

Complexity

Time: O(n + m). Space: O(1) - only pointers, nodes are spliced in place.

Approach 2: Recursive - Clearest Warm-Up

The Idea

The recursive definition mirrors the problem statement exactly. Base case: if either list is empty, the merge is the other list. Recursive case: the node with the smaller value becomes the head; its next is the merge of the rest of that list with the other list. Each call peels off one node and recurses on a smaller total, so it terminates.

Logic Flowchart

graph TD
    A["merge(a, b)"] --> B{"a == null?"}
    B -->|Yes| C["return b"]
    B -->|No| D{"b == null?"}
    D -->|Yes| E["return a"]
    D -->|No| F{"a.val <= b.val?"}
    F -->|Yes| G["a.next = merge(a.next, b); return a"]
    F -->|No| H["b.next = merge(a, b.next); return b"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the recursive merge. If either list is empty, return the other. Otherwise the smaller head's next becomes the merge of the rest of its list with the other list, and that head is returned.

Code

public static ListNode mergeTwoListsRecursive(ListNode a, ListNode b) {
    if (a == null) return b;                 // base case: nothing left in a
    if (b == null) return a;                 // base case: nothing left in b
    if (a.val <= b.val) {
        a.next = mergeTwoListsRecursive(a.next, b);   // a leads; merge the rest
        return a;
    } else {
        b.next = mergeTwoListsRecursive(a, b.next);   // b leads; merge the rest
        return b;
    }
}

// Usage: mergeTwoListsRecursive([1,2,4],[1,3,4]) -> [1,1,2,3,4,4]

This Java code merges recursively. The base cases return the non-empty list. Otherwise the smaller head's next is set to the recursive merge of the remainder, and that head is returned.

Step-by-Step Walkthrough

A frame-by-frame trace on list1 = [1,2,4], list2 = [1,3,4]:

graph LR
    F0["merge([1,2,4],[1,3,4])<br/>1<=1 → 1, merge([2,4],[1,3,4])"]
    F1["2>1 → 1, merge([2,4],[3,4])"]
    F2["2<=3 → 2, merge([4],[3,4])"]
    F3["4>3 → 3, merge([4],[4])<br/>4<=4 → 4, merge([],[4]) → [4]"]
    F4["unwind: 1,1,2,3,4,4"]
    F0 --> F1 --> F2 --> F3 --> F4

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F2 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F4 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough merges one-two-four and one-three-four. Each call picks the smaller head and recurses on the remainder, building one, one, two, three, four, four as the recursion unwinds.

Result: [1, 1, 2, 3, 4, 4].

Complexity

Time: O(n + m) - one call per node. Space: O(n + m) - recursion stack depth equals the total node count.

Complexity Comparison

Both are correct and linear. Iterative wins on space and is what you'd ship; recursive wins on clarity and is the better teaching vehicle. For these small constraints (≤ 50 nodes each) the recursion depth is trivial, so either is fine in an interview - but mention the stack cost when offering the recursive version.

Variations & Follow-ups

How does the recursion guarantee termination?

Every recursive call passes a list with at least one fewer node than before (one head is peeled off), and the base case fires when either list reaches null. Since the total node count strictly decreases each call, the recursion bottoms out after at most n + m calls.

Why is the recursion not backtracking?

There's only one path down - at each step you make a single choice (take the smaller head) and never reconsider it. Backtracking requires multiple branches per level with state restored between them. This problem has a single branch, so it's pure recursion: a clean stepping stone before the branching problems arrive.

When would the stack space matter?

With lists of length up to n + m, the recursion depth is n + m. For very long lists (millions of nodes) this risks a stack overflow, so the iterative version is safer at scale. At interview constraints it's a non-issue, but naming the tradeoff shows maturity.

What about edge cases?

• Both empty (Example 2): First base case returns the (empty) other list → null.
• One empty (Example 3): Base case returns the non-empty list unchanged.
• Equal values: <= takes from list1 on ties, which keeps it stable and avoids infinite loops.
• One list fully smaller: Its nodes are taken first, then the remainder is attached in one step.

Common Interview Pitfalls

• Forgetting a base case. Missing the null checks causes a NullPointerException or non-termination.
• Using < instead of <=. Either works for correctness here, but <= is the stable, conventional choice.
• Creating new nodes. The problem says splice existing nodes; allocating new ones wastes memory and is unnecessary.
• Losing the head in the iterative version. Always return dummy.next, not dummy.

Why This Topic Matters

Merge Two Sorted Lists is the canonical "recursion that reads like its own definition" problem. It teaches the two essentials of every recursive solution - a base case that stops the descent and a recursive case that does a little work and delegates the rest - without the added complexity of branching or state restoration. Get comfortable here and the branching problems become far less intimidating.

The next topic, Pow(x, n), introduces divide-and-conquer recursion: computing x raised to the n in O(log n) instead of O(n) by squaring. Where merging delegated a problem of size n-1, fast power delegates a problem of size n/2 - the first taste of recursion that shrinks the problem geometrically, which is where recursion starts to deliver dramatic speedups.

Back to DSA Mastery - Interview Prep, End to End