Merge ListsMerging lists

01Why it exists

Reach for it when you see:Two (or k) already-sorted sequences, merging, taking the smallest one, merge sort, dummy + tail, k-way merge.

02The core idea

Combining two sorted lists into one sorted list takes a single observation: the smallest node overall has to be the head of one of the two lists. Take the smaller head away and what remains is still two sorted lists, so you repeat exactly the same thing. That is a merge. Every node is compared once and attached once, which makes it O(n + m).

In code, a dummy node serves as the start of the result and tail points at the last node of the result so far. Each round attaches the smaller head to tail.next, advances tail, and advances the head of the list it came from. When one list runs out, the rest of the other is already linked together, so just point tail.next at it instead of attaching node by node. No new nodes are created, only pointers rewired, so the extra space is O(1).

Merging k lists means picking the smallest of k heads every round. Keep those k heads in a min-heap: popping the smallest costs O(log k) and pushing its successor back costs O(log k), for O(N log k) in total. The alternative is to merge them in pairs, tournament style, which has the same complexity.

Turn it around and, with the merge as a building block, you get merge sort on a linked list: fast and slow pointers find the midpoint and cut there, each half is sorted recursively, and the two are merged. This is the standard way to sort a linked list, and it ties together the previous three lessons — fast and slow pointers, recursion, and merging.

03The algorithm

1. 1Create dummy and set tail = dummy. The dummy node makes attaching the first node look exactly like attaching every node after it.
2. 2while a and b: compare a.val with b.val, attach the smaller node to tail.next, advance that list's pointer, and set tail = tail.next. Take a on ties, so the result stays stable.
3. 3After the loop, tail.next = a or b attaches whichever list still has nodes, all in one move.
4. 4Return dummy.next, not dummy.
5. 5For k lists, push every list's head into a min-heap (Python needs an index as a tie-breaker), then repeatedly pop the smallest, attach it, and push its next.

04Interactive demo

Step through how two lists merge: each step compares the two heads and attaches the smaller one to the end of the result; once a list runs out, everything left in the other is attached in a single move.

05Code

The iterative and recursive versions of merging two lists, the heap-based merge of k lists, and merge sort on a linked list, which uses the merge as a building block.

import heapq

# Merge two sorted lists: dummy + tail, attaching the smaller head each time. O(n + m)
def merge_two(a, b):
    dummy = tail = ListNode(0)
    while a and b:
        if a.val <= b.val:          # take a on ties, which keeps the merge stable
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b              # attach whatever is left in one go
    return dummy.next


# Recursive version: merge(a, b) = the smaller node + merge(the rest)
def merge_two_rec(a, b):
    if not a: return b
    if not b: return a
    if a.val <= b.val:
        a.next = merge_two_rec(a.next, b)
        return a
    b.next = merge_two_rec(a, b.next)
    return b


# Merge k lists: a min-heap holds every list's head, and the smallest comes off each time. O(N log k)
def merge_k(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))   # i stops the heap comparing nodes
    dummy = tail = ListNode(0)
    while heap:
        _, i, node = heapq.heappop(heap)
        tail.next = tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next


# Merge sort on a list: fast and slow pointers halve it, each half is sorted recursively, then merged. O(n log n), O(log n) stack
def sort_list(head):
    if not head or not head.next:
        return head
    slow, fast = head, head.next
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    right, slow.next = slow.next, None      # cut it in the middle
    return merge_two(sort_list(head), sort_list(right))

06Practice

• LeetCode 21Merge Two Sorted ListsEasy
• LeetCode 88Merge Sorted Array (the array version: fill from the back)Easy
• LeetCode 148Sort List (merge sort on a linked list)Medium
• LeetCode 23Merge k Sorted Lists (with a heap)Hard
• LeetCode 2Add Two Numbers (a variation on walking two pointers together)Medium