Linked List Flattening

Description

Flattening turns a linked structure with two or more levels into one list. Two different problems share the name. One merges sorted sub-lists that hang off a top-level chain into one sorted list, a k-way merge. The other unfolds a multilevel doubly linked list so each child list appears right after its parent node, a depth-first walk that splices in place. Knowing which one you face decides the whole approach.

We'll go from simple to more technical:

1. The pattern: fold sorted sub-lists together with the two-list merge.
2. A second flavor: splice child lists in place, in depth-first order.
3. Where each kind of flattening shows up in production.
4. The pointer bugs: lost continuations and half-updated prev links.

The approach

In the first problem, each top-level node starts a sorted sub-list that runs along its child pointer. The top-level nodes are linked by next. You already know how to merge two sorted lists. So walk the top level and merge each sub-list into a growing result, one at a time. The only twist is that the sorted order follows child instead of next.

Three sub-lists hang off the top level: 3 9 15, 6 7 and 1 12.

The top level doesn't need to be in order: the sub-list starting at 1 comes last and still lands first.

Node flatten(Node head) {
    Node result = null;
    Node cur = head;
    while (cur != null) {
        Node nextTop = cur.next;      // remember before merging disturbs pointers
        result = mergeByChild(result, cur);
        cur = nextTop;
    }
    return result;
}
// mergeByChild is exactly linked-list-merge-technique's merge, just walking
// .child instead of .next

def flatten(head: Node | None) -> Node | None:
    result = None
    cur = head
    while cur is not None:
        next_top = cur.next          # remember before merging disturbs pointers
        result = merge_by_child(result, cur)
        cur = next_top
    return result
# merge_by_child is exactly linked-list-merge-technique's merge, just walking
# .child instead of .next

Save cur.next before merging. The merge rewires the nodes of cur's sub-list, and afterwards cur's own pointers may no longer lead where they did.

A second flavor: splicing in place, not merging by value

The second problem has nothing sorted in it. In a multilevel doubly linked list, any node may have a child chain, and that chain belongs right after the node. Children can have children too. The final order comes from position, not from comparing values. Walk the list. When a node has a child, push the node that used to follow it onto a stack, splice the child in, and keep walking. When a chain runs out, pop the stack and continue from there.

Say 1 <-> 2 <-> 3, where 2 has the child chain 5 <-> 6, and 5 has its own child 9. It flattens to 1, 2, 5, 9, 6, 3.

Node flatten(Node head) {
    Node curr = head;
    Deque<Node> stack = new ArrayDeque<>();
    while (curr != null) {
        if (curr.child != null) {
            if (curr.next != null) stack.push(curr.next);   // remember where to resume
            curr.next = curr.child;
            curr.next.prev = curr;                            // update BOTH directions at the seam
            curr.child = null;
        }
        if (curr.next == null && !stack.isEmpty()) {
            curr.next = stack.pop();
            curr.next.prev = curr;                            // same: both directions
        }
        curr = curr.next;
    }
    return head;
}

def flatten(head: Node | None) -> Node | None:
    curr = head
    stack = []
    while curr is not None:
        if curr.child is not None:
            if curr.next is not None:
                stack.append(curr.next)      # remember where to resume
            curr.next = curr.child
            curr.next.prev = curr            # update BOTH directions at the seam
            curr.child = None
        if curr.next is None and stack:
            curr.next = stack.pop()
            curr.next.prev = curr            # same: both directions
        curr = curr.next
    return head

Each splice joins two nodes. The list is doubly linked, so both links at the seam need updating: next going forward and prev coming back.

Where you'll see it

The first kind is a k-way merge: several sorted sources, such as search-index segments or sorted pages of API results, become one ranked stream. Folding them in one at a time is fine for a few. For many, pair them up or use a min-heap (see the Merge Technique skill). The second kind turns a nested document outline or a multi-level task list into one reading order. There, order comes from the structure, never from comparing values.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why save cur.next before merging the current sub-list?

2. Must the top-level nodes be sorted by their first values?

3. A flattened multilevel list reads correctly forwards but wrongly backwards. What's the likely cause?

Key takeaways

• Flattening sorted sub-lists reuses the two-list merge, one sub-list at a time.
• Save the next top-level node before the merge rewires the current one.
• Only the sub-lists must be sorted, not the top level.
• A multilevel doubly linked list has nothing to sort. Splice each child in where it hangs, and use a stack to remember where to resume.
• At every seam in a doubly linked list, update both next and prev.