Merge Two Sorted Lists

The problem

Given the heads of two sorted singly linked lists, splice them together into one sorted list and return its head. Reuse the existing nodes — don't allocate new ones.

class Node:
    def __init__(self, val: int, next: 'Node | None' = None):
        self.val = val
        self.next = next

Pattern: dummy node + tail pointer

A "dummy" head node simplifies edge cases — without it, you'd need a special case for "is this the first node we're attaching?" With the dummy, every iteration is uniform: extend tail by one node, advance whichever list contributed.

The dummy-node trick shows up anywhere you're building a linked structure by extension — merging, partitioning, deduplicating, inserting in a sorted position. Always reach for it.

Solution

def merge(a: Node | None, b: Node | None) -> Node | None:
    dummy = Node(0)
    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 if a else b      # attach whichever still has nodes
    return dummy.next

Trace

a:  1 -> 3 -> 5
b:  2 -> 4

dummy -> ?
tail = dummy

iter 1: 1 <= 2, tail.next = a (Node 1), a = 3->5, tail = Node 1
        dummy -> 1
iter 2: 3 > 2, tail.next = b (Node 2), b = 4, tail = Node 2
        dummy -> 1 -> 2
iter 3: 3 <= 4, tail.next = a (Node 3), a = 5, tail = Node 3
        dummy -> 1 -> 2 -> 3
iter 4: 5 > 4, tail.next = b (Node 4), b = None, tail = Node 4
        dummy -> 1 -> 2 -> 3 -> 4
End of loop (b is None). tail.next = a = Node 5.
dummy -> 1 -> 2 -> 3 -> 4 -> 5

return dummy.next = Node 1

Complexity

• Time: O(n + m). Each node visited once.
• Space: O(1) — no new nodes, just pointer juggling.

Variations worth knowing

• Recursive version: if a.val <= b.val: a.next = merge(a.next, b); return a else b.next = merge(a, b.next); return b. Clean, but uses O(n + m) stack space.
• Merge K Sorted Lists — a heap of heads; O((n+m+...) · log k).
• Sort a Linked List (Merge Sort) — merge sort is the natural fit, since splitting and merging are both cheap on linked lists. O(n log n); O(log n) recursive or O(1) bottom-up.