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.
Intuition
Depth-first order is exactly the flattened order: node, then its child list, then its former next. A stack remembers the interrupted next while we dive into a child — pop it back when the child branch is exhausted.
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
Walk with a stack
At each node: if it has a child, push its next (may be null-skipped) and rewire next to the child. The child pointer is cleared.
Resume on dead ends
When next is null and the stack isn't empty, pop the saved node and splice it after the current node, fixing both directions.
Keep prev consistent
Every rewire sets next.prev too — the doubly-linked invariant is maintained throughout.
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.