Flatten a Multilevel Doubly Linked List
A medium Linked List interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Linked List
- Sheets
- 1
- Core for
- 4 roles
The problem
Some nodes of this doubly linked list carry a child link to another doubly linked list, which may have children of its own. Pull every level up into one flat doubly linked list, placing each child list right after the node that owns it, and clear every child link.
Example 1
- Input
- [[2,[4,5]],[1,[]]]
- Output
- [2,4,5,1]
Example 2
- Input
- [[5,[6,7]],[8,[]]]
- Output
- [5,6,7,8]
Example 3
- Input
- [[3,[]],[9,[]],[4,[]]]
- Output
- [3,9,4]
Constraints
- 0 <= n <= 1000
How to think about it
Updated 2026-09-29Child branches act like recursive function calls or pre-order depth-first traversals. Whenever a child pointer is encountered, splice the child sublist directly between the current node and its existing next node, carrying forward the original next pointer at the child branch's tail.
Approaches, worst first
Stack-based traversal
time O(n) · space O(d)
Traverse nodes while maintaining an explicit stack of suspended next pointers. When encountering a child, push curr.next onto the stack, point curr.next to child, and nullify curr.child. When hitting a tail, pop from the stack and reattach.
Iterative splicing in placeWrite this one
time O(n) · space O(1)
Walk forward along the list. Whenever curr has a child, find the tail of that child branch, connect that tail to curr.next, wire curr.next to the child, clear curr.child, and ensure all prev pointers are synchronized. Continue the walk naturally through the flattened nodes.
Where people lose marks · 3
- Forgetting to clear `curr.child = null` after flattening leaves dangling child pointers that violate single-level doubly linked list invariants.
- Failing to set the child's `prev` pointer to `curr` breaks bidirectional navigation.
- If `curr.next` was originally null, connecting the child tail to `curr.next` must guard against dereferencing null to set `next.prev`.
The theory behind it
Linked List — the ground this problem stands on. All Linked List problems
What Linked List is
A linked list is a chain of separate cargo cars connected by coupling hooks, scattered anywhere across memory rather than sitting in a tidy contiguous row. Each car, called a node, holds a single piece of data and a pointer directing traffic to the address of the next car in line. Because nodes connect only by directional links, jumping straight to the tenth car is impossible without walking past the first nine.
When to reach for it
Choose a linked list when a problem requires frequent insertions and deletions at known positions without shifting whole blocks of surrounding memory. Problems mentioning pointer splicing, reversing subsequences in place, merging sorted streams, or detecting cycles in linear chains strongly point here. It is ideal when total capacity is unpredictable and memory allocation must happen one individual node at a time.
How the pattern works
Think in terms of pointer rewiring before dereferencing. Keep a dummy head node pointing to the start of the list so modifications to the initial item do not require separate edge logic. Always save references to neighboring nodes into temporary variables before cutting or redirecting forward links. When diagnosing loops or locating middle nodes, advance two references simultaneously at differing velocities so traversal completes without supplementary storage.
More Linked List problems
Target Roles
Core requirement for 4 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .