AlgoMaster Logo

Flatten a Multilevel Doubly Linked List

Last Updated: April 1, 2026

medium
3 min read

Understanding the Problem

At first glance, this looks like a tree-to-list conversion problem, and that intuition is spot on. The multilevel structure is essentially a tree where each node can have both a "next sibling" (the next pointer) and a "first child" (the child pointer). Our job is to splice every child chain into the main list, right after the parent node.

The tricky part is handling nested children. A child list can itself have children, forming arbitrarily deep nesting. So whatever approach we use needs to handle recursion or repeated traversal until every child pointer has been flattened away.

Here is the key observation: when we encounter a node with a child, we need to insert the entire child chain between that node and its next node. After insertion, the child pointer should be set to null. If the child chain itself has children, those will be encountered and flattened as we continue traversing the now-merged list.

Key Constraints:

  • Number of nodes <= 1000 → With n up to 1000, even O(n^2) is under a million operations. But O(n) is clearly achievable and preferred.
  • 1 <= Node.val <= 10^5 → Values are positive integers. Not particularly relevant to the algorithm, but confirms no special sentinel values.
  • The structure is a multilevel doubly linked list → We need to handle prev, next, and child pointers correctly. Forgetting to null out the child pointer or update prev pointers are common bugs.

Approach 1: DFS with Stack

Intuition

The multilevel structure is really a tree disguised as linked lists. The next pointer is like a right sibling, and the child pointer is like a left child. Flattening means doing a pre-order DFS traversal and linking all visited nodes into a single doubly linked list.

A stack-based DFS gives us explicit control over the traversal order. When we encounter a node, we push its next onto the stack (to revisit later) and then push its child (to visit immediately). Since a stack is LIFO, pushing next first and child second ensures we process the child before the next sibling, which is exactly the order we want.

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 to track nodes. But the next pointers already exist in the list itself. What if we walked to the tail of each child chain and stitched it directly to the next node?

Approach 2: Iterative In-Place (Optimal)

Intuition

Instead of using a stack, we can flatten the list in-place by iterating through it. When we find a node with a child, we do three things: find the tail of the child chain, connect the tail to the node's next, and connect the node to the child. Then we null out the child pointer and keep walking forward.

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