AlgoMaster Logo

Flatten a Multilevel Doubly Linked List

mediumFrequency5 min readUpdated June 23, 2026

Understanding the Problem

This is a tree-to-list conversion in disguise. The multilevel structure is a tree where each node has a "next sibling" (the next pointer) and a "first child" (the child pointer). Flattening it means splicing every child chain into the main list, right after its parent node.

The complication is nested children. A child list can have children of its own, forming arbitrarily deep nesting, so the solution has to keep flattening until every child pointer is gone.

When we reach a node with a child, the child chain has to be inserted between that node and its next node, and the child pointer cleared afterward. If the child chain has children of its own, those are flattened the same way once they become part of the main list.

Key Constraints:

  • Number of nodes <= 1000 → The list is small, but the splice-in-place approach below runs in O(n) with O(1) extra space, so there is no reason to settle for anything slower.
  • The structure is a multilevel doubly linked list → All three pointers (prev, next, child) must stay consistent. Two recurring bugs are forgetting to null out the child pointer after splicing and forgetting to fix the prev pointer of the node that follows the spliced chain.

Approach 1: DFS with Stack

Intuition

Flattening visits nodes in pre-order: a node, then its child subtree, then its next sibling. Linking nodes in that visit order produces the required single-level list.

A stack makes the order explicit. When we process a node, we push its next first and its child second. Because the stack is LIFO, the child comes off the stack before the next sibling, so the child chain gets linked in first. Pushing the next sibling before descending into the child is what lets us return to the sibling after the entire child subtree has been flattened.

Algorithm

  1. If the head is null, return null.
  2. Create a stack and push the head.
  3. Create a dummy prev node to simplify pointer management.
  4. While the stack is not empty:
    • Pop a node from the stack.
    • Link it to prev (set prev.next = curr, curr.prev = prev).
    • If the node has a next, push next onto the stack.
    • If the node has a child, push child onto the stack, then set the node's child to null.
    • Update prev = curr.
  5. Detach the dummy node: set head.prev = null.
  6. Return the head.

Example Walkthrough

1Initialize: push head onto stack. Stack=[1]
1
pop
2
3
4
5
6
null
1/6

Code

The stack uses O(n) extra space. The next approach removes it by reusing the pointers already in the list: it walks to the tail of each child chain and stitches that tail directly onto the parent's next node.

Approach 2: Iterative In-Place (Optimal)

Intuition

We can flatten the list in place during a single forward walk, with no stack. When the current node has a child, we splice the child chain in: find the tail of the child chain, point the current node at the child, point the child back at the current node, then connect the tail to whatever the current node used to point at. After clearing the child pointer, we continue walking from the current node, which now leads into the just-spliced chain.

Walking forward into the spliced chain instead of skipping past it is what handles nested children. A child two levels deep becomes part of the main list as soon as its parent is spliced in, so the same loop reaches it on a later iteration with no special handling.

Algorithm

  1. Start with a pointer curr at the head.
  2. While curr is not null:
    • If curr has a child:

a. Save curr.next as next.

b. Walk to the tail of the child chain.

c. Connect curr.next = curr.child and curr.child.prev = curr.

d. Connect tail.next = next and, if next is not null, next.prev = tail.

e. Set curr.child = null.

  • Move curr = curr.next.
  1. Return the head.

Example Walkthrough:

1Initial: curr=1. Nodes 3 and 8 have children.
1
curr
2
3
4
5
6
null
1/7

Code