Merge Two Sorted Lists

Before we start

This is one of the most fundamental operations in computer science — it is the "merge" in merge sort. Master it on linked lists and you will understand merge sort deeply enough to implement it on arrays, on lists, and eventually extend it to K lists using a heap. By the end you will be able to:

• Write the two-list merge from memory with a dummy head node.
• Trace the pointer dance step by step.
• Extend the idea to Merge K Sorted Lists using a min-heap.

Picture this first (no code yet)

The actual problem

Merge Two Sorted Lists (LC #21):

Given the heads of two sorted linked lists l1 and l2, merge them into one sorted list and return its head.

l1: 1 → 2 → 4
l2: 1 → 3 → 4
Output: 1 → 1 → 2 → 3 → 4 → 4

First, the slow way (so you feel the pain)

Collect all values from both lists into an array, sort the array, build a new linked list. O((n+m) log(n+m)) for the sort, O(n+m) extra space for the array. The comparison-based merge is O(n+m) time, O(1) extra space (just a few pointer variables) — no sorting, no extra array.

The turning point

The one idea to remember

The code, line by line

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)   # dummy eliminates "is the result list empty?" checks
    tail  = dummy         # tail always points to the last node of the merged list

    while l1 and l2:      # while both lists have remaining nodes
        if l1.val <= l2.val:
            tail.next = l1     # link smaller node
            l1 = l1.next       # advance l1
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next       # advance tail to the newly linked node

    # at least one list is now empty — attach the other
    tail.next = l1 if l1 else l2

    return dummy.next          # skip the dummy node

Line by line:

• dummy = ListNode(0) — a sentinel that lets tail.next = ... work even for the very first node, with no special "is result empty?" check.
• tail = dummy — tail starts at dummy and advances with every node added.
• while l1 and l2: — keep comparing while both lists are non-empty.
• tail.next = l1 — we are not creating a new node; we are rewiring l1's existing node into the merged list.
• tail = tail.next — must advance tail after each link, or tail.next would always overwrite the same connection.
• tail.next = l1 if l1 else l2 — one line handles the remainder; l1 and l2 are already sorted, so the remaining nodes are all valid and in order.
• return dummy.next — the dummy node itself isn't part of the answer.

Watch it happen, frame by frame

l1: 1 → 2 → 4, l2: 1 → 3 → 4

dummy → ?     tail = dummy

Iter 1: l1.val=1 == l2.val=1 → pick l1 (<=).
  tail.next = node1(l1). l1 → node2. tail → node1.
  merged so far: dummy → 1

Iter 2: l1.val=2, l2.val=1 → pick l2.
  tail.next = node1(l2). l2 → node3. tail → node1(l2).
  merged so far: dummy → 1 → 1

Iter 3: l1.val=2, l2.val=3 → pick l1.
  tail.next = node2(l1). l1 → node4(l1). tail → node2.
  merged so far: dummy → 1 → 1 → 2

Iter 4: l1.val=4, l2.val=3 → pick l2.
  tail.next = node3. l2 → node4(l2). tail → node3.
  merged so far: dummy → 1 → 1 → 2 → 3

Iter 5: l1.val=4, l2.val=4 → pick l1 (<=).
  tail.next = node4(l1). l1 → None. tail → node4(l1).
  merged so far: dummy → 1 → 1 → 2 → 3 → 4

Loop exits (l1 is None).
tail.next = l2 = node4(l2).

Final: 1 → 1 → 2 → 3 → 4 → 4  ✅

Recursive version (elegant, O(n+m) stack space)

def mergeTwoLists_recursive(l1, l2):
    if not l1: return l2
    if not l2: return l1
    if l1.val <= l2.val:
        l1.next = mergeTwoLists_recursive(l1.next, l2)
        return l1
    else:
        l2.next = mergeTwoLists_recursive(l1, l2.next)
        return l2

Beautiful, but uses O(n+m) stack space. Prefer the iterative version for long lists in production.

Extension: Merge K Sorted Lists (LC #23)

Given K sorted linked lists, merge all of them into one sorted list.

Naive: merge pairs repeatedly. K lists × n nodes each. Merge l1+l2 → n+n = 2n. Merge result + l3 → 3n. Total work: n + 2n + 3n + … + Kn = O(K² × n). For K=1000 and n=1000 that is 1 billion operations.

Better: min-heap. Push the head of each list into a min-heap. Always extract the minimum (O(log K)), link it to the result, and push the extracted node's next (if it exists) back into the heap.

import heapq

def mergeKLists(lists):
    dummy = ListNode(0)
    tail  = dummy
    heap  = []

    # Initialise heap with head of each non-empty list
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))   # (value, index, node)

    while heap:
        val, i, node = heapq.heappop(heap)    # extract minimum
        tail.next = node
        tail = tail.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

    return dummy.next

Why (node.val, i, node)? Python's heap compares tuples element by element. If two nodes have the same value, it would try to compare the nodes themselves — which fails (ListNode has no < operator). The index i breaks ties without comparing nodes.

Complexity: O(N log K) where N = total nodes, K = number of lists. For K=1000 and N=10⁶, that is 10⁷ operations — 100× faster than the naive approach.

Where to spot this pattern

Trigger words:

• "merge two sorted lists/arrays"
• "merge k sorted lists"
• "sort a linked list" — merge sort: split at middle, sort halves, merge
• "find the median of a stream" — conceptually similar (Chapter 9.4)

Common traps

dummy = ListNode(0);  tail = dummy

while l1 and l2:
    if l1.val <= l2.val:
        tail.next = l1;  l1 = l1.next
    else:
        tail.next = l2;  l2 = l2.next
    tail = tail.next        # ← must advance tail!

tail.next = l1 if l1 else l2
return dummy.next

Check yourself

result = None
if l1.val <= l2.val:
    result = l1; l1 = l1.next
else:
    result = l2; l2 = l2.next
tail = result

Practice problems

Next up: Remove Nth Node from End — the N-gap two-pointer trick that finds the node to delete in a single pass without knowing the list length.