Flatten a Multilevel Doubly Linked List
Flatten a Multilevel Doubly Linked List: nodes have next, prev and a possible child sublist (itself multilevel). Flatten into one level, children spliced in right after their parent.
- The number of Nodes will not exceed 1000.
- 1 <= Node.val <= 10⁵
Intuition
To flatten a multilevel doubly linked list, each node has next, prev, and possibly a child pointing to another list that may itself have children. The result must be a single level where each child list is spliced in immediately after its parent.
The ordering that the problem describes is exactly depth-first order: visit a node, then everything in its child list, then whatever followed it on its own level. Recognising that turns an unfamiliar pointer-rewiring exercise into a traversal you already know.
The difficulty is remembering where to resume. When you dive into a child list, the node that used to follow the parent still has to appear — after the entire child branch is exhausted, however deeply it nests. That is what a stack is for:
- Push the interrupted next before descending into a child, and pop it when the branch runs out.
When the current node has a child, rewire next to point at the child and clear the child pointer, since the flattened list must have none left. When next becomes null and the stack is not empty, pop the saved node and splice it on.
Every rewire touches two pointers, not one. The list is doubly linked, so each time you set a.next = b you must also set b.prev = a, or the backward chain quietly breaks while the forward one looks correct.
A child pointer is a branch, so this is a depth-first traversal wearing a linked-list costume. The stack holds what to come back to: when you dive into a child, push the node you deferred. That's the same explicit-stack pattern you'd use to convert any recursive DFS into an iterative one.
Approach
Before reading on: price up what the direct approach costs here, then ask which pointers must be saved before you overwrite anything. Aim for O(n) time and O(d) space.
Recognise the order as depth-first
Node, then its child list in full, then its original next — that is a depth-first walk. The whole problem is producing that order while rewiring pointers in place, which is why a stack rather than a queue is the right structure.
Walk with an explicit stack
Move a cursor along the list. The stack holds nodes whose turn has been deferred because a child list interrupted them. Using an explicit stack rather than recursion avoids overflow on a deeply nested input.
On a child, save the next and descend
When the current node has a child, push node.next onto the stack if it is non-null, then set node.next = node.child and clear node.child = null. Leaving the child pointer set is the most common bug — the list would still be multilevel by the problem's definition.
On a dead end, resume from the stack
When next is null and the stack is non-empty, pop the saved node and attach it after the current one. That resumes the outer level at the correct point, however deep the branch was.
Fix prev on every rewire
Every time you set a.next = b, also set b.prev = a. The doubly-linked invariant must hold throughout — a forward chain that looks right while the backward chain is broken passes a casual read of the output and fails the real test.
Cost of the flattening
Every node is visited once and pushed at most once, giving O(n) time. Space is O(d) for the stack, where d is the nesting depth — O(n) in the worst case of a list where every node has a child.
Solution & live demo
Common pitfalls
Attaching the child without saving next
cur.next = cur.child cur.child = None
if cur.next: stack.append(cur.next) cur.next = cur.child cur.child = None
Overwriting next drops the entire remainder of the current level — those nodes are simply lost from the output. The deferred continuation has to be stacked before the pointer is reassigned.
Leaving the child pointer set
cur.next = cur.child
cur.next = cur.child cur.child.prev = cur cur.child = None
The problem requires all child pointers to be null in the flattened list — a node reachable through both next and child is still multilevel. The prev link matters too: this is a doubly linked list, so every splice has to be wired in both directions.
Popping the stack while next is still non-null
elif stack:
nxt = stack.pop()elif not cur.next and stack:
nxt = stack.pop()A deferred branch may only resume once the current one is exhausted; resuming early interleaves the levels. The stack is a return address, and you return only at the end of the path.
Edge cases
Nothing to push; the child simply continues the list.
Return null immediately.