How Do You Flatten a Multilevel Linked List?
Learn how to flatten a multilevel doubly linked list with child pointers using depth-first splicing, with code and tips.
Expected Interview Answer
You flatten a multilevel doubly linked list, where nodes can have a child pointer to a separate sublist in addition to next and prev, by depth-first traversal: whenever a node has a child, splice the entire child sublist in between that node and its original next, recursively flatten the child first, then continue, producing a single-level doubly linked list in O(n) time and O(1) extra space (beyond recursion or an explicit stack).
The core idea is that each child sublist behaves like a detour: when you hit a node with a child, you must fully explore and flatten that child branch and insert it immediately after the current node before continuing to the current node’s original next. This is naturally implemented either recursively or with an explicit stack that pushes the current next pointer before diving into the child, so traversal can resume there once the child branch is exhausted. Every splice must correctly relink prev pointers on both ends of the insertion, and the child pointer on the node that had one must be cleared to null since the result is a single-level list. The pattern mirrors a preorder traversal of a tree where next is the primary child and child is the secondary branch explored immediately.
- O(n) time, visiting each node once
- O(1) extra space with an in-place iterative approach (excluding call/explicit stack)
- Produces a fully valid doubly linked list with correct prev pointers
- Directly reusable pattern for any nested-list flattening problem
AI Mentor Explanation
A tour itinerary lists matches in order, but some matches also have a “warm-up fixtures” sub-itinerary attached, like a detour before continuing the main tour. Flattening means, whenever you hit a match with warm-up fixtures, you fully insert that entire warm-up sequence right after the match and before returning to the next scheduled main-tour match, then clear the sub-itinerary link since it is now part of the single combined schedule. If a warm-up fixture itself has its own nested warm-ups, you handle those first before returning to the outer level, exactly like diving into a branch before resuming the trunk.
Step-by-Step Explanation
Step 1
Traverse the list node by node
Walk using next, checking each node for a non-null child pointer.
Step 2
On finding a child, save the original next
Remember node.next before rewiring, so traversal can resume there after the child branch.
Step 3
Splice the flattened child in
Recursively (or iteratively) flatten the child, then link node -> child -> ... -> saved next, fixing prev pointers on both seams.
Step 4
Clear the child pointer and continue
Set node.child to null, then continue traversal into what is now node.next.
What Interviewer Expects
- Describe the depth-first, insert-immediately-after pattern clearly
- Correctly handle prev pointer relinking on both splice seams
- Handle nested children (a child’s node also having a child) correctly
- State O(n) time and discuss the O(1) vs stack/recursion space tradeoff
Common Mistakes
- Forgetting to save the original next pointer before splicing, losing the rest of the list
- Not clearing the child pointer after flattening, leaving stale references
- Breaking prev pointers when splicing, producing an invalid doubly linked list
- Not recursing into a nested child (a child of a child) before continuing the outer traversal
Best Answer (HR Friendly)
“I walk the list and whenever a node has a child branch, I fully flatten that branch first and splice it in right after the current node, before continuing on to what was originally next. It is like handling a detour completely before getting back on the main road, and I make sure to fix up the previous pointers on both ends of every splice.”
Code Example
class Node:
def __init__(self, val, prev=None, next=None, child=None):
self.val = val
self.prev = prev
self.next = next
self.child = child
def flatten(head):
if not head:
return head
current = head
while current:
if current.child:
next_node = current.next
child_head = flatten(current.child)
current.next = child_head
child_head.prev = current
current.child = None
tail = child_head
while tail.next:
tail = tail.next
tail.next = next_node
if next_node:
next_node.prev = tail
current = current.next
return headFollow-up Questions
- How would you convert this recursive approach into an iterative one using an explicit stack?
- How would you flatten this back into separate levels given the flattened list?
- What extra bookkeeping do you need to correctly maintain prev pointers?
- How does this problem relate to a preorder traversal of a tree?
MCQ Practice
1. What must you save before diving into a node’s child branch?
The original next must be saved so traversal can resume there once the entire child branch has been spliced in.
2. After splicing a flattened child branch in, what must be set to null?
The child pointer must be cleared since the result should be a single-level list with no remaining child branches.
3. What traversal order does this flattening algorithm resemble?
It processes a node, then fully explores its child branch before continuing to the original next, matching a preorder depth-first pattern.
Flash Cards
What must you save before flattening a node’s child? — The node’s original next pointer, to resume traversal after the child branch.
What happens to the child pointer after a branch is spliced in? — It is set to null, since the result is a single-level list.
What is the time complexity of flattening a multilevel list? — O(n), visiting every node across all levels exactly once.
What traversal pattern does this algorithm follow? — A depth-first, preorder-style pattern where child branches are fully resolved before continuing to next.