Community Problem

Flatten a Multilevel Doubly Linked List

Difficulty: Medium

Flatten a doubly-linked list whose nodes may have a child pointer to another doubly-linked list, producing a single-level list via DFS or an explicit stack.

Flatten a Multilevel Doubly Linked List

Flatten a doubly-linked list whose nodes may have a child pointer to another doubly-linked list, producing a single-level list via DFS or an explicit stack.

MEDIUM

Free

linked-list

stack

recursion

By @vikramokoro

January 11, 2026

Updated May 20, 2026

493 views

4.5 (13)

I lifted this from a coworker's L5 onsite at a major data-platform company; the bug they saw most often was forgetting to clear the child pointer after splicing. The recursive DFS solution is the cleanest write-up; the explicit-stack iterative version is what survives the question "can you do it without recursion?".

Flatten a Multilevel Doubly Linked List

You are given a doubly-linked list where, in addition to the next and prev pointers, each node may have a child pointer that points to the head of another doubly-linked list (potentially with its own children). Flatten the list so it becomes a single-level doubly-linked list. The flattened list should appear as if you had performed a depth-first traversal: when a node has a child, you splice the entire child list right after the node, then continue with what was originally node.next. The child pointers should all be set to null in the result.

Examples

Example 1:

Input: head = [1, 2, 3, 4, 5, 6] with 3.child = [7, 8, 9, 10] and 8.child = [11, 12].
Output: [1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6]
Explanation: At node 3, we descend into [7, 8, 9, 10]. At node 8, we descend into [11, 12]. After exhausting depth, we resume.

Example 2:

Input: head = [1, 2] with 1.child = [3].
Output: [1, 3, 2]
Explanation: After 1, splice [3] (its child), then resume with 2.

Example 3:

Input: head = []
Output: []
Explanation: Empty input.

Example 4:

Input: head = [1, 2, 3], no children.
Output: [1, 2, 3]
Explanation: A flat list is already flat.

Constraints

The number of nodes does not exceed 1000.
1 <= Node.val <= 10^5
All children pointers form a valid tree (no cycles).
The result must be a doubly-linked list with proper prev pointers.

Follow-up

The recursive DFS is O(n) time and O(d) stack space where d is the maximum nesting depth. Can you write an iterative version with an explicit stack that is O(n) time and O(d) auxiliary?

Solution

JavaScript

Python

Hints

0/4

Hint 1

Hint 2

Hint 3

Hint 4

Solution Walkthrough

Approach

The target order is exactly the pre-order DFS of the multilevel structure: visit a node, descend into its child sub-list before continuing to its next sibling. The recursive write-up is short and clean; the iterative version with an explicit stack is what survives the no-recursion follow-up.

Key insight

When we encounter a node with a child, we want to splice the child sub-list IMMEDIATELY after the current node, then continue. Whatever was previously cur.next needs to be remembered for later (after we exhaust the spliced sub-list). A stack of saved continuations matches the LIFO nesting of children perfectly.

Algorithm

If head is null, return null.
Initialize an empty stack and cur = head.
While cur !== null:
- If cur.child !== null:
  
  If cur.next !== null: push cur.next onto the stack (continuation).
  
  Splice: cur.next = cur.child, cur.child.prev = cur, cur.child = null.
- If cur.next === null and the stack is non-empty: pop a continuation, splice it: cur.next = continuation, continuation.prev = cur.
- Advance cur = cur.next.
Return head.

Complexity

Text

Metric  Value
------  -----------------------------
Time    O(n)
Space   O(d) auxiliary, d = max depth

Each node is visited exactly once. The stack holds at most one continuation per level of nesting.

Why it works

The loop invariant is: the prefix from head up to and including cur is correctly flattened (each prev and next consistent), and the stack holds the LIFO sequence of pending continuations from outer levels. When we encounter a child, we save the current sibling chain on the stack and dive into the child. When we exhaust the current level (reach a node with cur.next === null), the most recently saved continuation is exactly what should come next, so we pop and splice. The pre-order property holds because we always finish the entire child sub-list before resuming the parent.

Pitfalls

Forgetting to set cur.child = null. The result is a multilevel list, not a flat one; some test harnesses explicitly check this.
Forgetting to fix prev pointers (cur.child.prev = cur and continuation.prev = cur). The doubly-linked structure needs both directions consistent.
Pushing cur.next even when it is null: extra null values in the stack confuse the resume logic. Guard with if (cur.next !== null).
Recursive write-up base case: if the child sub-list is empty (null), the recursion bottoms out and the parent's next continues unchanged. The iterative version does not have this branch because the if (cur.child !== null) already filters.

Solution Code

All Problems