Merge Two Sorted Lists

Merge Two Sorted Lists is the linked-list version of the merge step inside merge sort. It is a gentle introduction to two ideas you will reuse constantly: walking two pointers in lockstep, and using a dummy head to dodge annoying edge cases.

The idea

Both lists are already sorted, so the smallest unused value is always at one of the two heads. Look at both heads, take the smaller one, and move that list's pointer forward. Repeat. When one list runs out, the other list is already sorted, so just attach all of it at once.

The one nuisance is the very first node: it has no "previous" node to link from. The classic trick is a dummy head — a throwaway node we always have in hand. We attach merged nodes after the dummy, and at the end the real answer is dummy.next. This removes every "is this the first node?" special case.

A tail pointer remembers the end of the merged list so each new node is an O(1) append. Ties (equal heads) can go to either list; taking from a keeps the merge stable.

Walk through it

Step through the animation. Pointers a and b sit on the heads of the two rows. At each compare, the smaller head drops into the tail row and its pointer slides forward. When a empties after appending 4, the loop stops and the leftover 4 in b is attached in one move.

Pseudocode

make a dummy node; let tail = dummy
while both a and b are non-empty:
    if a.val <= b.val:
        tail.next = a; advance a
    else:
        tail.next = b; advance b
    advance tail to the node we just attached
tail.next = whichever list is left (a or b)   # the other is empty
return dummy.next                              # skip the dummy

The loop runs while both lists have nodes. The moment one empties, the remaining list is appended wholesale.

The Python solution

def merge(a, b):
    dummy = ListNode()
    tail = dummy
    while a and b:
        if a.val <= b.val:
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

• dummy is a placeholder node so the first append needs no special case; tail always points at the last node of the merged list.
• The while a and b loop keeps going only while both lists still have a node to compare.
• a.val <= b.val picks the smaller head. <= (not <) sends ties to a, which makes the merge stable.
• After attaching a node we slide that list's pointer (a = a.next or b = b.next) and then tail = tail.next.
• tail.next = a or b attaches the non-empty leftover list in one shot (a or b is whichever is not None).
• We return dummy.next — the real head, skipping the placeholder.

Complexity

We touch every node exactly once, so time is O(n + m) where n and m are the two lengths. We only rewire existing nodes — no new list is allocated — so extra space is O(1) (the dummy is a single node).

When this pattern shows up

Practice