Flatten a Linked List

Before we start

Flattening a linked list sounds simple until you realize a node can have a child pointer that branches into an entirely separate list — and each child can have its own children. This creates a tree-like structure masquerading as a list. By the end you will be able to:

• Explain why a stack is a natural fit for saving "deferred" work when you branch into a child.
• Write both the stack-based and the inline-insert approaches from memory.
• Trace a three-level multilevel list, step by step.

Picture this first (no code yet)

The actual problem

Flatten a Multilevel Doubly Linked List (LC #430):

Each node has val, prev, next, and child. The child field optionally points to a separate doubly linked sublist. Flatten the list so all nodes appear in a single-level doubly linked list, with nodes in depth-first (DFS) order.

Example:

Level 1: 1 ⟷ 2 ⟷ 3 ⟷ 4 ⟷ 5 ⟷ 6
                   |
Level 2:           7 ⟷ 8 ⟷ 9 ⟷ 10
                           |
Level 3:                   11 ⟷ 12

Expected output (DFS order):

1 ⟷ 2 ⟷ 3 ⟷ 7 ⟷ 8 ⟷ 11 ⟷ 12 ⟷ 9 ⟷ 10 ⟷ 4 ⟷ 5 ⟷ 6

After visiting node 3, you dive into child 7 before continuing to 4.

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

Recursive DFS: when you hit a node with a child, recursively flatten the child list first, find the tail of the flattened child, then reconnect. This works conceptually but function-call overhead on deeply nested input can overflow the call stack. For 10,000 levels, the Python default recursion limit (~1000) throws a RecursionError. The iterative stack avoids this entirely.

The turning point

The one idea to remember

Approach 1: Stack (explicit DFS)

def flatten(head):
    if not head:
        return head

    stack = []
    cur = head

    while cur:
        if cur.child:
            if cur.next:
                stack.append(cur.next)   # save the continuation

            cur.next  = cur.child        # dive into child
            cur.child.prev = cur         # fix prev pointer
            cur.child = None             # clear child field

        elif not cur.next and stack:
            # dead end: no next, no child → pop saved continuation
            saved = stack.pop()
            cur.next   = saved
            saved.prev = cur             # fix prev pointer

        cur = cur.next

    return head

Line-by-line narration:

1. stack = [] — our bookmark shelf for deferred continuations.
2. cur = head — start from the front.
3. if cur.child: — found a branch. Must go down before going right.
4. stack.append(cur.next) — only push if there is a next; avoids pushing None.
5. cur.next = cur.child — redirect next to child list.
6. cur.child.prev = cur — keep the doubly-linked invariant.
7. cur.child = None — clean up: node no longer has a child.
8. elif not cur.next and stack: — reached end of a sub-list; pop bookmark.
9. cur.next = saved; saved.prev = cur — re-attach the saved continuation.
10. cur = cur.next — advance one step.

Approach 2: Inline insert (elegant, no stack)

Instead of a stack, insert the entire child list inline between cur and cur.next:

def flatten(head):
    cur = head
    while cur:
        if cur.child:
            child_head = cur.child
            child_tail = child_head
            while child_tail.next:   # walk to the tail of child list
                child_tail = child_tail.next

            # insert child list between cur and cur.next
            child_tail.next = cur.next
            if cur.next:
                cur.next.prev = child_tail
            cur.next  = child_head
            child_head.prev = cur
            cur.child = None

        cur = cur.next
    return head

Trade-off: simpler to read, but finding child_tail is O(child length) at each step — potentially O(n²) for deeply nested equal-length chains. The stack approach is always O(n) total.

Watch it happen, frame by frame

Input (abbreviated to track the key moments):

1 ⟷ 2 ⟷ 3 ⟷ 4
        |
        7 ⟷ 8

Using the stack approach:

cur=1: no child, no stack. cur=2.
cur=2: no child, no stack. cur=3.
cur=3: child=7. Push (4) onto stack.
       3.next=7, 7.prev=3, 3.child=None.
       cur=4  ... wait, cur=cur.next=7 now.

Let me re-trace:
cur=3: has child(7).
  stack.append(3.next=4)   → stack=[4]
  3.next = 7, 7.prev = 3, 3.child = None
  cur = 3.next = 7

cur=7: no child.
  cur.next=8 exists → don't pop. cur=8.

cur=8: no child.
  cur.next = None AND stack=[4] → pop.
  saved=4. 8.next=4, 4.prev=8.
  cur = 8.next = 4.

cur=4: no child, no stack. cur=None. Exit.

Final: 1⟷2⟷3⟷7⟷8⟷4  ✅

Full three-level trace summary

For the original example with three levels:

Level 1: 1⟷2⟷3⟷4⟷5⟷6  (3 has child 7)
Level 2: 7⟷8⟷9⟷10       (8 has child 11)
Level 3: 11⟷12

Stack evolution:

• At node 3: push(4), follow child 7. Stack = [4].
• At node 8: push(9), follow child 11. Stack = [4, 9].
• At node 12: no next, pop(9). Continue from 9. Stack = [4].
• At node 10: no next, pop(4). Continue from 4. Stack = [].
• At node 6: no next, stack empty. Done.

Result: 1⟷2⟷3⟷7⟷8⟷11⟷12⟷9⟷10⟷4⟷5⟷6 ✅

A different "flatten" variant: sorted lists merging vertically

Some problems define a linked list where each node also has a down pointer pointing to a sorted vertical chain. Flatten by merging these sorted chains bottom-up.

def flatten_sorted(root):
    if not root or not root.next:
        return root

    # recursively flatten from the right
    root.next = flatten_sorted(root.next)

    # merge current node's down-list with the flattened right
    root = merge_sorted(root, root.next)
    return root

def merge_sorted(a, b):
    if not a: return b
    if not b: return a
    if a.val <= b.val:
        a.down = merge_sorted(a.down, b)
        return a
    else:
        b.down = merge_sorted(a, b.down)
        return b

This variant appears in GFG-style interview questions ("Flatten a Linked List" where each node has a right and a down pointer and the down-chains are sorted). The merge is the same merge pattern from Chapter 4.4, applied to down pointers instead of next.

Common traps

stack, cur = [], head
while cur:
    if cur.child:
        if cur.next: stack.append(cur.next)
        cur.next = cur.child
        cur.child.prev = cur
        cur.child = None
    elif not cur.next and stack:
        saved = stack.pop()
        cur.next = saved
        saved.prev = cur
    cur = cur.next
return head

Check yourself

Practice problems

Next up: Add Two Numbers as a Linked List — where each node stores one digit and you must carry correctly across different-length numbers.