Flatten Multilevel Doubly Linked List | Linked List

Overview

Flatten a multilevel doubly linked list means converting a structure where each node has val, prev, next, and optionally child (a pointer to the head of another list) into a single-level doubly linked list. The typical rule: when you see a node with a child, flatten the child list and insert it after the current node (before the current node's original next). Then continue from the end of the flattened child. Order is depth-first: main list until child, then full child list, then rest of main list.

Key idea: Traverse the list; when a node has a child, you need to (1) remember the current node's next, (2) connect current to child head (and child head's prev to current), (3) flatten the child list (recursively or iteratively), (4) find the tail of the child list and connect it to the saved next (and next's prev to that tail), (5) set node.child = null. Use a stack or recursion to handle nested children.

When to Use

Flatten multilevel list — Exact problem (e.g. LeetCode 430).
Depth-first flattening of nested list structure — Same pattern.

How It Works

Iterative with stack:

Use a stack to store "pending next" when we go into a child. Start with curr = head.
While curr is not null or stack is not empty: if curr has a child, push curr.next onto the stack, set curr.next = curr.child, set child.prev = curr, set curr.child = null, and set curr = curr.child (or curr.next). Otherwise, if curr.next is null and stack is not empty, pop and set curr.next = popped (and set prev). Then curr = curr.next.
Maintain prev/next and prev pointers correctly at every link.

Recursive: Flatten(node): while node: if node has child, save next = node.next, connect node to child, recursively flatten child and get its tail, connect tail to next, set node.child = null, node = next; else node = node.next. Return the tail of the flattened segment.

Example 1: Flatten Multilevel (Iterative with Stack)

Problem: You are given a doubly linked list with nodes that may have a child. Flatten the list so that all nodes appear in a single-level doubly linked list.

function flatten(head: Node | null): Node | null {
  if (head === null) return null;
  const stack: (Node | null)[] = [];
  let curr: Node | null = head;
  while (curr !== null) {
    if (curr.child !== null) {
      if (curr.next !== null) stack.push(curr.next);
      curr.next = curr.child;
      curr.child.prev = curr;
      curr.child = null;
    }
    if (curr.next === null && stack.length > 0) {
      const next = stack.pop()!;
      curr.next = next;
      next.prev = curr;
    }
    curr = curr.next;
  }
  return head;
}

Time: O(n) over all nodes, Space: O(depth) for the stack.

Example 2: Recursive Flatten (Return Tail)

Idea: flatten(node) flattens from node onward and returns the tail of the flattened list. When node has child: connect node to child, tail = flatten(child), connect tail to node.next, clear child, then flatten from node.next and return that tail (or tail if node.next is null).

Edge Cases

No children — List unchanged; just return head.
Child at tail — node.next is null; after flattening child, connect child's tail to null; no stack push.
Deep nesting — Stack or recursion depth equals max nesting level.

Common Mistakes

Forgetting prev — This is a doubly linked list; set child.prev = curr and (when connecting tail to next) next.prev = tail.
Not clearing child — Set node.child = null after flattening so the structure is a single list.
Losing the rest of the list — When going into a child, push curr.next so you can reconnect after the child list ends.

Time and Space Complexity

Time: O(n) where n is total nodes (each node processed once).
Space: O(depth) for stack or recursion.

Summary

Flatten multilevel: When node has child, save next, connect node to child, flatten child, connect child's tail to saved next, clear child; use stack or recursion for nesting.
See Doubly Linked List for prev/next handling.

Flatten a Multilevel Doubly Linked List