Flatten a Linked List

Flatten a Linked List takes a list whose nodes each hang their own sorted sub-list and folds everything into a single sorted list. It is the classic way to practice the merge step of merge sort on linked structures, where you splice pointers instead of copying values.

The slow way first

The blunt approach: collect every value into an array, sort it, then rebuild a fresh bottom-linked list. That works, but sorting throws away a gift the input already hands us — each column is already sorted. Re-sorting n values costs O(n log n) and ignores the structure entirely.

The question to ask: if every piece is already sorted, how do I combine sorted pieces without re-sorting? You merge them, exactly like merge sort's combine step.

The idea: merge columns right to left

Treat each column (a head and its bottom list) as one sorted list. Recurse along next to the rightmost head first — that column, having no next, is already a flat sorted list and becomes the base. Then walk back leftward, and at each head merge its column into the accumulated flattened list. Two sorted bottom-lists merge by repeatedly taking the smaller front node and splicing it onto the result.

The key insight: because both lists going into each merge are already sorted, one linear pass interleaves them. Folding columns in one at a time keeps the running result sorted the whole way.

Walk through it

Step through the animation. We first recurse to the last column 1 → 4 → 8 and seed the result with it. Then we step left and merge 2 → 6 into it, slotting 2 and 6 into place. Finally we merge 5 → 7, and every value lands in its sorted slot, producing one bottom-linked list 1 → 2 → 4 → 5 → 6 → 7 → 8.

Pseudocode

flatten(head):
    if head is empty or has no next column:
        return head                       # single sorted column = done
    head.next = flatten(head.next)        # flatten everything to the right first
    head = merge(head, head.next)         # fold this column into that result
    return head
 
merge(a, b):                              # both lists are sorted by bottom
    walk a and b together, always taking the smaller front node
    link it onto the result via bottom
    when one runs out, attach the remainder of the other
    return the merged head

The Python solution

def flatten(head):
    if head is None or head.next is None:
        return head
    head.next = flatten(head.next)
    head = merge(head, head.next)
    return head
 
def merge(a, b):
    dummy = tail = Node(0)
    while a and b:
        if a.val <= b.val:
            tail.bottom, a = a, a.bottom
        else:
            tail.bottom, b = b, b.bottom
        tail = tail.bottom
    tail.bottom = a or b
    return dummy.bottom

• The base case in line 2 stops the recursion at the rightmost column — a single sorted list needs no merging.
• Line 4 flattens everything to the right of the current head before touching the current column, so merge always receives two already-sorted lists.
• Line 5 merges the current column into that flattened remainder; the result becomes the new head.
• In merge, the dummy node lets us build the result without special-casing the first link; tail always points at the last placed node.
• Each loop turn compares the two front values and splices the smaller one onto tail.bottom, then advances that list. When one list empties, line 16 attaches the rest of the other in one move.

Complexity

Here n is the total number of nodes and k is the number of columns. Each value is touched once per merge it participates in, so the work is O(n · k) in the splicing approach (often written O(n²) when columns are comparable in size). The extra space is just the O(k) recursion depth — we splice existing nodes rather than copying them.

When this pattern shows up

Practice