Merge Two Sorted Linked Lists Explained: Tracing 1→2→4 and 1→3→4

Imagine you are handed two separate chains of data that are already sorted in ascending order. For our locked working example, we have list1 starting at node $1\to 2\to 4$ and list2 starting at node $1\to 3\to 4$. If you need to combine them into a single sorted stream, your first instinct might be to unpack everything into an array, sort it from scratch, and rebuild a brand new linked list. But that wastes time and memory.

Linked lists give us a superpower: individual nodes can be re-routed instantly by updating pointers, provided we know how to weave them together in order. Without a systematic strategy, you risk losing track of tail references, breaking chain connections, or getting stuck trying to compare unsorted chunks. We want to arrive at our expected final result, $1\to 1\to 2\to 3\to 4\to 4$, by directly stitching the existing nodes together in a single pass.

// Given setup for our locked example:
// list1: 1 -> 2 -> 4
// list2: 1 -> 3 -> 4
// Goal: produce 1 -> 1 -> 2 -> 3 -> 4 -> 4 without allocating new nodes.

When we want to combine list1 ($\{1\to 2\to 4\}$) and list2 ($\{1\to 3\to 4\}$) without allocating new nodes, we cannot use standard array indexing. Instead, we use a single sliding pointer—often named tail—to stitch the existing nodes together in ascending order.

To simplify the logic of attaching the very first node, we introduce a dummy head node. This temporary anchor gives our tail pointer a reliable starting point, so we never have to write special conditional code for the first successful comparison.

As our pointers advance through the sequences, we compare the current value of list1 against list2. Whichever value is smaller gets linked to tail.next, and that list's pointer steps forward while tail advances to follow it.

To see our mental model in action, let us trace through the locked working example with $\text{list1}=1\to 2\to 4$ and $\text{list2}=1\to 3\to 4$. We initialize a $\text{dummy}$ node with value 0 and set our $\text{tail}$ pointer equal to $\text{dummy}$. Let $\text{p1}$ point to the head of $\text{list1}$ (1) and $\text{p2}$ point to the head of $\text{list2}$ (1).

Both $\text{p1.val}$ (1) and $\text{p2.val}$ (1) are equal. By convention, we can take from $\text{list1}$ first. We attach $\text{p1}$ to $\text{tail.next}$, advance $\text{tail}$ to $\text{p1}$, and advance $\text{p1}$ to 2.
- Intermediate State: $\text{dummy}\to 1$ (from $\text{list1}$)
- Active Pointers: $\text{tail}\to 1$, $\text{p1}\to 2$, $\text{p2}\to 1$

Now we compare $\text{p1.val}$ (2) with $\text{p2.val}$ (1). Since $1<2$, we attach $\text{p2}$ to $\text{tail.next}$, advance $\text{tail}$ to $\text{p2}$, and advance $\text{p2}$ to 3.
- Intermediate State: $\text{dummy}\to 1\to 1$ (second 1 from $\text{list2}$)
- Active Pointers: $\text{tail}\to 1$ ($\text{list2}$'s first node), $\text{p1}\to 2$, $\text{p2}\to 3$

Comparing $\text{p1.val}$ (2) and $\text{p2.val}$ (3): $2<3$, so we attach $\text{p1}$ (2), advance $\text{tail}$ to $\text{p1}$, and advance $\text{p1}$ to 4.
- Intermediate State: $\text{dummy}\to 1\to 1\to 2$
- Active Pointers: $\text{tail}\to 2$, $\text{p1}\to 4$, $\text{p2}\to 3$

Next, comparing $\text{p1.val}$ (4) and $\text{p2.val}$ (3): $3<4$, so we attach $\text{p2}$ (3), advance $\text{tail}$ to $\text{p2}$, and advance $\text{p2}$ to 4.
- Intermediate State: $\text{dummy}\to 1\to 1\to 2\to 3$
- Active Pointers: $\text{tail}\to 3$, $\text{p1}\to 4$, $\text{p2}\to 4$

Both $\text{p1}$ and $\text{p2}$ now sit at value 4. Comparing them yields a tie; we take $\text{p1}$ (4), advance $\text{tail}$ and $\text{p1}$ (so $\text{p1}$ becomes $\text{null}$). Then, since $\text{p2}$ still holds a final node (4), we attach the remainder of $\text{p2}$ directly to $\text{tail.next}$.
- Result: $\text{dummy.next}$ yields the fully merged sorted list: $1\to 1\to 2\to 3\to 4\to 4$.

Try this: Given list1 = 1->2->4 and list2 = 1->3->4, what is the exact node value attached to tail.next during Step 3 when comparing p1.val (2) and p2.val (3)?

Now that you have seen how a dummy head and advancing pointers successfully weave list1 = 1→2→4 and list2 = 1→3→4 into 1→1→2→3→4→4 by reusing existing nodes in $O(n+m)$ time, it is time to transfer this pattern. The core lesson of the merge routine is not just about sorting; it is about structural pointer redirection where you never allocate new nodes, but instead rewire existing .next references in a single pass.

Consider what happens if we change the target slightly. Suppose instead of merging two sorted lists, you are given $k$ sorted linked lists, or you need to merge two sorted lists where one list contains duplicate values that you want to filter out on the fly. The dummy node anchor and the tracking tail pointer remain your primary tools because they prevent you from losing the head of the newly formed sequence. Whenever you manipulate sorted linked lists, always ask: Where is my immutable entry point, and which pointer is currently responsible for attaching the next smallest element?

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
    dummy = ListNode(-1)
    tail = dummy
    # Implement the merge loop using list1 and list2
    return dummy.next