vault

Merge Two Sorted Lists

15 min read

Merge Two Sorted Lists

Given two sorted singly linked lists L₁ and L₂, return a single sorted linked list containing all the nodes of both — by rewiring next pointers in place, no new node allocations. The algorithm is the two-pointer merge: walk both lists in lockstep, repeatedly choose the smaller front node, append it to the output, advance the chosen list. Same logic as Merge Sort’s merge step (CLRS §2.3.1) but applied to linked storage rather than arrays — and crucially O(1) auxiliary space because we splice existing nodes rather than copy values. The classic LC 21 question; also the building block for K-Way Merge on linked lists, and a frequent vehicle for testing the sentinel/dummy head pattern that simplifies almost every linked-list problem with a non-obvious head node.

1. Intuition — The Two-Stack Card Sort

Imagine you have two stacks of playing cards on the table, each already sorted ascending from top to bottom. You want to combine them into a single sorted stack.

Look at the top card of each stack. Whichever is smaller, place face-up on a new “output” pile. Look at the new tops of both stacks. Whichever is smaller, place on the output pile. Repeat. When one stack runs out, dump the rest of the other on top of the output pile (it’s already sorted, so no further work is needed).

This is exactly the merge step of Merge Sort — and it’s also exactly what we do for linked lists, except instead of physically moving cards onto a new pile, we rewire pointers so the existing nodes form a single chain. No allocation, no copying, just next-pointer reassignments.

The output pile starts off as a sentinel (a “dummy head” with no payload) so we have a stable reference even before any real node is chosen. After the merge, the real head is the sentinel’s next.

2. Tiny Worked Example

Merge L₁: 1 → 4 → 5 and L₂: 1 → 3 → 4.

Set up a sentinel and a tail pointer that always points to the last node of the output so far.

Initial state

  L1:        [1] → [4] → [5] → null
  L2:        [1] → [3] → [4] → null

  sentinel:  [DUMMY | next=null]
  tail:      → DUMMY

Iteration 1

Compare L1.value (1) and L2.value (1). Tie — convention is to take from L1 (we’ll discuss the stability angle in §6).

  Choose L1's first node ([1]):
    tail.next := L1   →   sentinel.next = [1 from L1]
    tail := L1                  (tail now points at [1 from L1])
    L1 := L1.next               (L1 now points at [4])

  Output (so far): DUMMY → [1₁] → ?
                                 ↑
                              L1=[4]   L2=[1₂]

I’m using subscript ₁/₂ to disambiguate the two 1s.

Iteration 2

Compare L1.value (4) and L2.value (1). L2 is smaller, so take from L2.

  tail.next := L2   →   [1₁].next = [1₂]
  tail := L2
  L2 := L2.next

  Output: DUMMY → [1₁] → [1₂] → ?
                                ↑
                            L1=[4]   L2=[3]

Iteration 3

Compare L1.value (4) and L2.value (3). L2 smaller.

  tail.next := L2   →   [1₂].next = [3]
  tail := L2 = [3]
  L2 := L2.next = [4₂]

  Output: DUMMY → [1₁] → [1₂] → [3] → ?
                                       ↑
                                   L1=[4₁]   L2=[4₂]

Iteration 4

Compare L1.value (4₁) and L2.value (4₂). Tie — take from L1 by convention.

  tail.next := L1   →   [3].next = [4₁]
  tail := [4₁]
  L1 := [5]

  Output: DUMMY → [1₁] → [1₂] → [3] → [4₁] → ?
                                              ↑
                                          L1=[5]   L2=[4₂]

Iteration 5

Compare L1.value (5) and L2.value (4₂). L2 smaller.

  tail.next := L2   →   [4₁].next = [4₂]
  tail := [4₂]
  L2 := L2.next = null

  Output: DUMMY → [1₁] → [1₂] → [3] → [4₁] → [4₂] → ?
                                                     ↑
                                              L1=[5]   L2=null

Cleanup — One List Exhausted

L2 == null, so we attach all of L1 (which is already sorted) to the tail:

  tail.next := L1   →   [4₂].next = [5]

  Output: DUMMY → [1₁] → [1₂] → [3] → [4₁] → [4₂] → [5] → null

Return

return sentinel.next — i.e., the node [1₁]. The sentinel itself is not part of the result; it served only to give us a uniform “tail” reference during the merge.

Six pointer reassignments (one per real node), no allocations, O(n+m) total time, O(1) auxiliary space.

3. Pseudocode

merge(L1, L2):
    sentinel := new Node(value=null)
    tail := sentinel

    while L1 != null and L2 != null:
        if L1.value <= L2.value:           # <= preserves stability (L1 wins ties)
            tail.next := L1
            L1 := L1.next
        else:
            tail.next := L2
            L2 := L2.next
        tail := tail.next

    # One of L1, L2 is null; the other is the sorted suffix to splice on.
    if L1 != null:
        tail.next := L1
    else:
        tail.next := L2

    return sentinel.next

The sentinel pattern is doing two jobs: (a) providing a starting point for tail before any real node is appended, and (b) giving us a single reference to return sentinel.next regardless of whether L1 or L2 contributed the first node.

4. Python Implementation — Iterative

from typing import Optional
 
class Node:
    """Singly-linked list node — same shape as in [[Singly Linked List]] and friends."""
    def __init__(self, value, next: Optional["Node"] = None):
        self.value = value
        self.next = next
 
def merge_two_sorted(l1: Optional[Node], l2: Optional[Node]) -> Optional[Node]:
    """LC 21. Merge two sorted singly linked lists, in place, into one sorted list.
    O(n + m) time, O(1) auxiliary space."""
    sentinel = Node(value=None)         # dummy head — discard at the end
    tail = sentinel
 
    while l1 is not None and l2 is not None:
        if l1.value <= l2.value:        # <= for stability — L1 wins ties
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
 
    # Splice on the remaining tail of whichever list still has nodes.
    tail.next = l1 if l1 is not None else l2
 
    return sentinel.next

A few implementation choices worth flagging:

  • Sentinel. Without it, the first iteration would need a special branch (“is the output empty?”) to set the result-head; instead, every iteration uniformly does tail.next = chosen; tail = tail.next. The sentinel is allocated once at the top and discarded at the end.
  • <= not <. This makes the merge stable with respect to lists where equal-value nodes from L1 should come before equal-value nodes from L2. This matters most when this routine is called from Merge Sort on linked lists, where stability is one of merge sort’s selling points.
  • Final splice. When one list is exhausted, the other is non-empty and already sorted — splice the entire remainder in O(1) by setting tail.next = remaining_list. No need to copy node-by-node.

5. Recursive Variant

A more concise version that mirrors the recursive merge in CLRS:

def merge_two_sorted_recursive(l1: Optional[Node], l2: Optional[Node]) -> Optional[Node]:
    """O(n + m) time, O(n + m) call-stack space."""
    if l1 is None:
        return l2
    if l2 is None:
        return l1
    if l1.value <= l2.value:
        l1.next = merge_two_sorted_recursive(l1.next, l2)
        return l1
    else:
        l2.next = merge_two_sorted_recursive(l1, l2.next)
        return l2

Each recursive call peels off one front node and recurses on the rest. The base case is “one input is empty — return the other.” The recursion depth is n + m (one frame per node), so the stack space is O(n + m) — the same asymptotic class as the iterative O(1) solution, but with a much larger constant and a real stack-overflow risk for long lists. Lead with the iterative version in interviews unless explicitly asked for recursion.

6. Stability — Why <= Matters

A stable merge preserves the relative order of equal-keyed elements. If L1 contributes a (4, "Alice") and L2 contributes a (4, "Bob") (both with key 4), a stable merge always emits Alice before Bob — because Alice came from L1, the “earlier” input.

The <= comparison ensures this: when l1.value == l2.value, the condition l1.value <= l2.value is true, so we take from L1. If we used <, the equal case would fall to the else branch and take from L2 first — unstable.

This matters when the merge step is used inside Merge Sort on linked lists. Merge sort’s stability is one of its main advantages over Quicksort; that stability is delivered by exactly this <= choice in the merge subroutine.

7. Complexity

MetricIterativeRecursive
TimeO(n + m)O(n + m)
Auxiliary spaceO(1)O(n + m) (call stack)
Allocations1 (sentinel)n + m (one frame per node)
Stable?Yes (with <=)Yes (with <=)

Why O(n+m) time: every iteration either advances L1 or advances L2, never both, never neither. Each list is walked at most once. Total iterations ≤ n + m. The final splice is O(1). Hence O(n+m).

Why O(1) auxiliary space (iterative): we allocate exactly one sentinel node (and free it at the end — actually, we just stop holding a reference; in GC’d languages the sentinel is reclaimed). Beyond that, only a constant number of pointer variables (tail, l1, l2). The merged list reuses the input nodes.

Why this is optimal: any algorithm that produces all n + m nodes in sorted order must touch each at least once (Ω(n+m) lower bound). The iterative merge achieves this with a constant per-node overhead (one comparison, one assignment, one pointer advance). Asymptotically tight.

8. Use Cases

8.1 Building Block for Linked-List Merge Sort

Merge Sort applied to a linked list:

  1. Find the middle of the list using slow/fast pointers (see Singly Linked List §4.4).
  2. Split into two halves at the middle.
  3. Recursively sort each half.
  4. Merge the two sorted halves using this routine.

Because each of these steps is O(1) auxiliary (or O(log n) for the recursion stack), linked-list merge sort runs in O(n log n) time and O(log n) space — strictly better than copying to an array and back.

This is one of the few places linked lists win in practice over arrays: array merge sort needs O(n) auxiliary space for the merge buffer, while linked-list merge sort needs only the recursion stack. For sorting linked lists as linked lists, merge sort is the canonical choice.

8.2 K-Way Merge

K-Way Merge generalizes from 2 to k sorted inputs. The two natural approaches:

  • Sequential pairwise merge. Merge L1 and L2; merge the result with L3; merge with L4; … O(k · n) total work where n is the average list length, because the running merged list grows and is re-walked each time.
  • Min-heap-based merge. Place the head of each of k lists into a min-heap; repeatedly pop the smallest, advance that list, push the new front. O(N log k) total, where N = total node count. Strictly better than sequential pairwise for large k.
  • Tournament / divide-and-conquer. Recursively merge pairs of lists, halving k each round. O(N log k) like the heap approach, but often with better constants.

The 2-list merge from this note is the leaf operation in approaches (a) and (c). Approach (b) doesn’t use the 2-list merge directly — it uses a heap of single-node fronts. See K-Way Merge for full discussion.

8.3 Database Sort-Merge Join

When two relations are already sorted (or sorted via an index) on the join key, the sort-merge join algorithm is essentially a two-list merge that emits matched pairs. The same O(n + m) linear-walk pattern, with comparison logic adapted to “match” rather than “select smaller.” This is a foundational join algorithm in every relational database; the linked-list version is the conceptual prototype.

8.4 Streaming Merge of Sorted Logs

Distributed systems frequently produce sorted-by-timestamp log streams from multiple machines. Merging them on a central collector for analysis is exactly this routine, generalized to k inputs. Frameworks like Apache Kafka’s compactor and the Linux sort -m flag both implement variants of merge.

9. Pitfalls

9.1 Forgetting the Sentinel

Without a sentinel, you need a special branch for the first iteration: “is the output empty? if so, set head; otherwise append to tail.” This adds an if to every loop iteration (or requires hoisting it out via a check before the loop). The sentinel eliminates this; the cost is one extra Node allocation. Always use the sentinel.

9.2 Forgetting the Final Splice

After the main loop, exactly one of l1 and l2 is non-null (the one with longer remaining suffix). You must attach this remainder to tail.next. Forgetting this step truncates the merged list at the length of the shorter input. A subtle bug that passes simple test cases (where both lists have the same length) and fails on asymmetric inputs.

9.3 Wrong Comparison Direction

if l1.value <= l2.value — choose L1. Some implementations write this backward (if l2.value < l1.value — choose L2), and confuse stability or off-by-one. Pick a direction and stick with it.

9.4 Using < Instead of <= and Losing Stability

Functionally either works (the merged list is sorted), but stability is broken with <. If the caller relies on stability (as merge sort does), this is a silent correctness bug — the output is sorted but elements with equal keys are reordered.

9.5 Allocating New Nodes Instead of Splicing

A common LeetCode-novice mistake:

# Anti-pattern: O(n+m) auxiliary space.
result = []
while l1 and l2:
    if l1.value <= l2.value:
        result.append(l1.value); l1 = l1.next
    else:
        result.append(l2.value); l2 = l2.next
# ... build a new list from `result` ...

This allocates n + m new nodes (or holds n + m values in a Python list before reconstructing), wasting O(n+m) space. The whole point of merge-on-linked-lists is to reuse the input nodes by rewiring pointers. Splice, don’t copy.

9.6 Returning the Sentinel Instead of sentinel.next

return sentinel returns a node whose value is None (or 0, or whatever your sentinel uses) followed by the actual sorted list — i.e., the result has a junk head. return sentinel.next skips the sentinel. Easy mistake; LeetCode tests catch it instantly because the first emitted value is wrong.

9.7 Mutating the Inputs When You Shouldn’t

This routine mutates l1 and l2 in place — the input lists no longer exist as separate lists after the merge. If the contract requires preserving the inputs, you’d have to copy each node before splicing — adding O(n+m) time and space. Read the problem statement; LC 21 explicitly allows in-place mutation, but production code may not.

9.8 Recursive Stack Overflow for Long Lists

The recursive variant uses one stack frame per node. Python’s default recursion limit is 1000; lists longer than that crash. Either raise the limit (sys.setrecursionlimit(10**7)), use an explicit stack, or — better — use the iterative version.

9.9 Cyclic Inputs

If either input has a cycle (e.g., L1’s tail points back into L1), the loop never terminates because neither list reaches null. Detect cycles first via Linked List Cycle Detection if cycle inputs are possible.

10. Diagram — Pointer State at Three Snapshots

SNAPSHOT 0 (start)

   l1 → [1] → [4] → [5] → null
   l2 → [1] → [3] → [4] → null
   sentinel → DUMMY (next=null)
   tail → DUMMY


SNAPSHOT 2 (after appending [1] from L1, then [1] from L2)

   l1 → [4] → [5] → null
   l2 → [3] → [4] → null
   sentinel → DUMMY → [1₁] → [1₂]
   tail              ──────────^


SNAPSHOT FINAL (after main loop and final splice)

   l1 → null     (consumed)
   l2 → null     (consumed)
   sentinel → DUMMY → [1₁] → [1₂] → [3] → [4₁] → [4₂] → [5] → null
   tail                                        ──────^

   return sentinel.next  →  [1₁]

flowchart LR
    S0[sentinel<br/>DUMMY] --> A0[1 from L1] --> B0[1 from L2] --> C0[3] --> D0[4 from L1] --> E0[4 from L2] --> F0[5] --> Z0[null]

What this diagram shows. Three snapshots in time. At Snapshot 0 the output is just the sentinel; both inputs are intact. At Snapshot 2, two nodes have been appended (the two 1s), one from each input, and the inputs have advanced. At the final snapshot, both inputs have been entirely consumed and spliced into a single chain reachable from sentinel.next. The mermaid diagram below the snapshots shows the final structure as a single sorted chain. Notice that no new value-carrying nodes were allocated — the same physical nodes that were originally in L1 and L2 now form the merged chain, just with their next pointers rewritten.

11. Common Interview Problems

ProblemLeetCodePattern
Merge Two Sorted ListsLC 21This note (the canonical question)
Merge K Sorted ListsLC 23K-Way Merge — heap-based or divide-and-conquer pairwise
Sort List (sort a linked list)LC 148Merge sort with this routine as the merge step
Add Two NumbersLC 2Pairwise sum with carry — same two-pointer skeleton
Intersection of Two Linked ListsLC 160Two-pointer walk with a length-equalizing trick
Merge IntervalsLC 56Same idea on arrays of intervals (not linked lists)

LC 21 is on virtually every “linked list 101” interview list. LC 23 (K-way merge) is the senior-level extension. Sort List (LC 148) ties the two together — it asks you to sort a linked list, the natural answer is merge sort, and the merge step is exactly LC 21 — a delightful example of how foundational this routine is.

12. Open Questions

  • Is there any in-place merging algorithm that beats O(n+m) time on linked lists? No — every node must be visited (Ω(n+m) lower bound) and pointers rewritten. The constants are already nearly optimal: one comparison, one assignment, one pointer advance per node.
  • When does it make sense to merge two linked lists by copying values into an array, sorting, and rebuilding? Almost never — array merge is O(n+m) too but with worse constants on linked-storage inputs.

13. See Also

Graph View

Backlinks