Flatten a Multilevel Doubly Linked List
Problem Statement
You are given the head of a multilevel doubly linked list. Each node has prev, next, and child pointers. A child pointer may point to the head of another doubly linked list, which may also contain child pointers. Flatten the structure so that all nodes appear in depth-first order in one doubly linked list. Every child pointer in the result must be null.
Input
The head of a multilevel doubly linked list. The ordinary chain uses next and prev, while child points to the head of a nested list.
Output
Return the head of a single-level doubly linked list in depth-first order, with correct prev and next links and every child pointer set to null.
Constraints
- •
The number of nodes is between 0 and 1000 - •
1 <= Node.val <= 10^5 - •
There are no cycles in next, prev, or child pointers
Examples
Example 1
head = 1 -> 2 -> 3 -> 4 -> 5 -> 6, with 3.child = 7 -> 8 -> 9 -> 10 and 8.child = 11 -> 12
1 -> 2 -> 3 -> 7 -> 8 -> 11 -> 12 -> 9 -> 10 -> 4 -> 5 -> 6Example 2
head = 1 -> 2, with 1.child = 3 -> 4
1 -> 3 -> 4 -> 2Learning Objectives
- Recognise a multilevel linked list as a depth-first traversal problem over node references.
- Splice a child list between a node and its original next node without losing either side.
- Maintain both directions of a doubly linked list after every local mutation.
- Use a stack to simulate recursion while preserving the correct return point.
Intuition
Pattern Recognition
The signal is the word flatten combined with child pointers. The result is not breadth-first by levels; it is preorder depth-first: visit the current node, then its child chain, then the original next chain. That means whenever a node has a child, the child list must be inserted before the node's saved next pointer.
The pointer trap is losing the saved next node. If curr.next is overwritten by curr.child before the original next is remembered, the algorithm has no way to return to the sibling chain. A stack solves this cleanly: push the original next before descending into the child, so the child chain is fully consumed before the sibling continues.
Common mistakes
- ×Forgetting to set **child** to **null** after splicing a child list into the main chain.
- ×Updating next pointers but not fixing the matching prev pointers.
- ×Losing the original next node when replacing it with the child head.
- ×Flattening by breadth-first levels instead of the required depth-first order.
Algorithm Explanation
Key idea
Perform a preorder depth-first traversal and rebuild the list as one doubly linked chain. A stack stores nodes that should be visited later. Push current.next first, then current.child, so the child is popped and processed before the sibling. A dummy predecessor lets every visited node be appended with the same two pointer assignments.
Pointer walkthrough
Consider 1 -> 2 -> 3, where 2.child -> 4 -> 5. When the traversal reaches 2, the original next node 3 is the return point, so it is saved on the stack. The child head 4 is processed next and linked as 2 <-> 4 <-> 5. After 5 finishes, the stack brings back 3, and the chain becomes 1 <-> 2 <-> 4 <-> 5 <-> 3. During this splice, 2.child is set to null, 4.prev -> 2, and 3.prev -> 5.
Algorithm
- If head is null, return null.
- Create a dummy node and set previous to the dummy. Push head onto a stack.
- While the stack is not empty, pop the next node to visit.
- Append it after previous by setting previous.next and current.prev.
- Push current.next if it exists, because it must be resumed after the child chain.
- Push current.child if it exists, then set current.child to null.
- Move previous to current. After the loop, detach the dummy and return the real head.
Solutions
Solution: Iterative depth-first splice with stack
Use this when you want explicit control over traversal order and want to avoid relying on the call stack for deeply nested child lists.
The stack holds future nodes in reverse visit order. By pushing the original next before the child, the child chain is processed first. Each popped node is appended to the flattened tail, its prev pointer is repaired, and its child pointer is cleared.
Step-by-step
- Use a dummy node as the predecessor before the flattened list.
- Push head, then repeatedly pop the next node in depth-first order.
- Link the popped node after the current flattened tail with both next and prev pointers.
- Push the popped node's original next pointer before pushing its child pointer.
- Clear the child pointer and advance the flattened tail.
- Detach the dummy by setting the real head's prev to null before returning.
O(n)
O(n)
Every node is popped and linked once; the stack can hold return points for many pending sibling chains.
Java implementation
Dry Run
Sample input
Input: 1 -> 2 -> 3, with 2.child -> 4 -> 5. Track the iterative stack solution. The top of the stack is shown first.
| step | popped node | stack after pushes | pointer action | flattened prefix |
|---|---|---|---|---|
| 1 | 1 | empty | Append 1 after dummy | 1 |
| 2 | 2 | 4, 3 | Append 2, save 3, descend to child 4, clear 2.child | 1 <-> 2 |
| 3 | 4 | 5, 3 | Append 4, save its next 5 | 1 <-> 2 <-> 4 |
| 4 | 5 | 3 | Append 5, no child remains | 1 <-> 2 <-> 4 <-> 5 |
| 5 | 3 | empty | Append saved sibling 3 and set 3.prev to 5 | 1 <-> 2 <-> 4 <-> 5 <-> 3 |
The stack preserves the return point 3 while the child chain 4 -> 5 is flattened. Every appended node receives a matching prev link, so the final list works in both directions.
Interview Tips
Draw the splice before coding. Say that when current.child exists, the child list must come before the saved current.next chain. With the stack approach, emphasize push order: push next first, child second. Also call out the two required cleanup steps, setting child to null and detaching the dummy's prev link from the real head.
Likely follow-ups
- How would you implement the same depth-first flattening recursively by returning the tail of each flattened child list?
- How would the output change if the interviewer asked for breadth-first flattening instead?
- How would you detect invalid input that contains a cycle through child pointers?
- Can you flatten in place while preserving a way to reconstruct the original multilevel structure?
Similar Problems
Key Takeaways
- Flattening is a depth-first traversal problem, not a level-order traversal problem.
- Save the original next pointer before descending into a child chain.
- Doubly linked rewiring must update both **next** and **prev** every time.
- Every child pointer must be cleared in the final single-level list.