21 · Merge Two Sorted Lists

Two sorted chains become one.

Two assembly lines feed sorted packages onto a single conveyor belt. At each step the operator compares the front item from each line, takes the smaller, and places it on the belt. When one line runs out, the remaining packages arrive already in order — they transfer without further comparison. A dummy head eliminates the first-attachment edge case, and a tail pointer tracks the growing chain. One pass through both lists. O(n + m) time. O(1) extra space.

Interactive

Watch two lists merge, node by node

Concept

Dummy head, tail pointer, front comparison

The algorithm maintains a single growing chain. A dummy sentinel node at the head removes the need for a special case when attaching the first real node. The tail pointer always sits at the end, ready to receive.

Dummy head

A temporary sentinel node created before the loop. Every selected node is attached through tail.Next — including the very first one. At the end, dummyHead.Next gives the real head of the merged list.

eliminates the first-node special case

Tail pointer

Always points to the last node in the merged chain. After attaching a new node via tail.Next = selectedNode, the tail advances to that node. The chain grows by one link each iteration.

tracks the growing end of the merged chain

Front comparison

At each step, compare the current front values of both input lists. The smaller value wins. When values are equal, list1.val ≤ list2.val takes from list1 — preserving the relative order of equal elements.

always takes the smaller front node
Algorithm

Compare, attach, advance — then append the remainder

The main loop runs while both lists have nodes. Each iteration compares the two front values, attaches the winner to the merged chain, and advances the winning list's pointer. When one list is exhausted, the other's entire remaining suffix is attached directly.

  1. 1

    Initialize

    Create a dummy head node. Set tail = dummyHead. Both input list pointers start at their respective heads.

  2. 2

    Compare front values

    While both list1 and list2 are non-null: compare list1.val and list2.val. Select the node with the smaller (or equal) value.

  3. 3

    Attach and advance

    Set tail.Next = selectedNode, then advance the selected list's pointer to its next node. Finally, move tail forward to the newly attached node.

  4. 4

    Append remaining suffix

    When one list is exhausted, set tail.Next to the other list's current node. The remaining suffix is already sorted, so no further comparisons are needed.

  5. 5

    Return result

    Return dummyHead.Next — the first real node of the merged list. The dummy head is discarded.

Edge Cases

When the merge is trivial

Three edge cases arise from degenerate inputs. The dummy-head pattern handles all of them without special-case branches.

One list is empty

When list1 or list2 is null, the while-loop body never executes. tail.Next is set to the non-null list, and the entire input is returned unchanged. Zero comparisons needed — the sorted list is already the answer.

Equal front values

When both front nodes have the same value, the ≤ comparison selects from list1. This is a deliberate choice — it preserves the relative order of equal elements, making the merge stable. Try the "all equal values" preset to see this in action.

Early exhaustion

When one list is much shorter, it runs out before the other. The comparison loop ends early, and the longer list's entire remaining suffix is attached in a single tail.Next operation — no element-by-element copying. Try the "early exhaustion" preset.