Flatten Multilevel Doubly Linked List — Stack-Based DFS Explained

Problem Statement#

You are given a doubly linked list, which contains nodes that have a next pointer, a prev pointer, and an additional child pointer. This child pointer may or may not point to a separate doubly linked list, also with these three kinds of pointers. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure. Given the head of the first level of the list, flatten the list so that all the nodes appear in a single-level, doubly linked list. Let curr be a node with a child list. The nodes in the child list should appear after curr and before curr.next in the flattened list. Return the head of the flattened list.

Constraints:

• The number of nodes in the list is in the range [0, 1000]
• 1 <= Node.val <= 10^5
• The depth of the nesting is at most 1000

Example 1:

Input:  head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Output: [1,2,3,7,8,11,12,9,10,4,5,6]

Example 2:

Input:  head = [1,2,null,3]
Output: [1,3,2]
Explanation: Node 1 has child 3. Flatten: 1->3->2.

Why This Problem Matters#

Flatten Multilevel Doubly Linked List (LeetCode 430) is a medium problem that Microsoft and Amazon use because it tests two things simultaneously: traversal of a recursive/nested data structure, and in-place pointer manipulation on a doubly linked list. Both are skills that appear constantly in systems programming.

The problem models a real data structure: hierarchical menus, nested outline documents, tree representations of nested lists. The child pointer is essentially an "expand this node into a sub-list" operation. Flattening it means performing a DFS and inlining each child list at the point of its parent node.

The explicit stack approach mirrors iterative DFS — a fundamental pattern for traversing hierarchical structures without recursion. When you encounter a node with a child, you push the next node onto the stack (to come back to it later), and then continue into the child list. This is exactly how an iterative DFS works with an explicit stack.

The problem also reinforces the importance of correctly maintaining prev pointers in a doubly linked list — an easy-to-miss requirement that turns a seemingly complete solution into an incorrect one.

The Core Insight#

Traverse the list node by node. When you encounter a node with a child:

1. Save node.next onto a stack (you'll resume from here later)
2. Connect node.next = node.child and node.child.prev = node
3. Clear node.child = None
4. Continue traversal into the child sub-list

When the current chain reaches a node where curr.next is None and the stack is non-empty:

1. Pop the saved next from the stack
2. Connect curr.next = popped and popped.prev = curr
3. Continue traversal

The stack effectively saves "where to resume" after each child list is exhausted.

Visual Dry Run#

Input: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6, with 3.child = 7 <-> 8 <-> 9 <-> 10, and 8.child = 11 <-> 12

Start: stack = [], curr = 1

Output: 1 <-> 2 <-> 3 <-> 7 <-> 8 <-> 11 <-> 12 <-> 9 <-> 10 <-> 4 <-> 5 <-> 6

Solution (Optimal)#

Python — Iterative Stack#

def flatten(head):
    if not head:
        return head
 
    stack = []
    curr = head
 
    while curr:
        if curr.child:
            # Save the rest of the current level
            if curr.next:
                stack.append(curr.next)
 
            # Insert child list after curr
            curr.next = curr.child
            curr.next.prev = curr
            curr.child = None  # clear the child pointer
 
        # If current node has no next and stack has saved nodes
        if not curr.next and stack:
            nxt = stack.pop()
            curr.next = nxt
            nxt.prev = curr
 
        curr = curr.next
 
    return head

Time complexity: O(n) — each node is visited exactly once.

Space complexity: O(d) where d is the maximum nesting depth (stack depth).

Python — Recursive DFS#

def flatten(head):
    def dfs(node):
        """Flatten from node onward, return the last node of the flattened list."""
        curr = node
        last = None
 
        while curr:
            if curr.child:
                child_head = curr.child
                child_last = dfs(child_head)  # flatten child list, get its last node
 
                nxt = curr.next
                curr.next = child_head
                child_head.prev = curr
                child_last.next = nxt
                if nxt:
                    nxt.prev = child_last
                curr.child = None
 
                last = child_last
                if nxt is None:
                    break
                curr = nxt
            else:
                last = curr
                curr = curr.next
 
        return last
 
    if not head:
        return head
    dfs(head)
    return head

JavaScript — Iterative Stack#

var flatten = function(head) {
    if (!head) return head;
 
    const stack = [];
    let curr = head;
 
    while (curr !== null) {
        if (curr.child !== null) {
            if (curr.next !== null) {
                stack.push(curr.next);
            }
            curr.next = curr.child;
            curr.next.prev = curr;
            curr.child = null;
        }
 
        if (curr.next === null && stack.length > 0) {
            const nxt = stack.pop();
            curr.next = nxt;
            nxt.prev = curr;
        }
 
        curr = curr.next;
    }
 
    return head;
};

Complexity:

Common Mistakes#

1. Forgetting to set prev pointers. This is a doubly linked list — every new connection requires updating both next and prev. Missing prev updates produces incorrect output silently (LeetCode may not catch it if the grader only checks next pointers, but it's wrong).

2. Forgetting to clear curr.child = None. After connecting the child to the current node's next, the original child pointer must be cleared. Leaving curr.child set means the flattened list still has child pointers pointing into the list — incorrect structure.

3. Pushing curr.next onto the stack even when curr.next is None. Only push if curr.next is non-null. Pushing None would later pop and try to connect None as a next node — causing errors.

4. Popping from the stack when curr.next is None and the stack is non-empty, but forgetting to set prev. When you reconnect a saved node: curr.next = popped; popped.prev = curr. Both assignments are required.

5. Infinite loop if child connects back to a parent node. The problem guarantees no cycles, but with cycles the traversal would loop forever. Assume the input is valid.

Interview Tips#

1. Relate to iterative DFS: "I'll use an explicit stack — this is essentially an iterative DFS where the stack saves the 'resume point' after each child list."

2. Draw the multilevel list: For any example, draw the hierarchy (parent level and child levels) visually. This makes the traversal order obvious.

3. Emphasize prev pointers: "Since it's a doubly linked list, every time I connect A -> B, I must also set B.prev = A."

4. Walk through the stack contents: Show what's on the stack after each child encounter and after each pop. This demonstrates you understand the algorithm mechanically.

5. Mention the recursive alternative: "A recursive approach has DFS flatten each child list and return the tail, which you can then connect to the saved next. Same complexity, different code style."

Follow-up Questions#

Q: What if the nesting can be arbitrarily deep? The iterative stack approach handles any depth without stack overflow (the Python call stack has a limit, but the explicit list-based stack doesn't). For very deep nesting, iterative is safer than recursive.

Q: What's the time complexity? O(n) — each node is visited exactly once. Whether via the iterative approach or recursion, every node is processed exactly once.

Q: How does this relate to tree flattening (LC 114)? LC 114 (Flatten Binary Tree to Linked List) flattens a binary tree to a singly linked list in pre-order. Same DFS concept but different data structure. Both use the "visit node, recurse into child, reconnect at tail" pattern.

Q: What if you want to flatten bottom-up instead of top-down? Process from the deepest level upward. This is the recursive approach — it implicitly flattens deeper levels first and returns the tail for connection.

Q: Is there an O(1) space solution? No — some auxiliary space is needed. Either the recursion stack or an explicit stack uses O(d) space where d is the nesting depth.

Key Takeaways#

• The iterative stack models DFS: when you encounter a child, push curr.next (resume point) and descend into the child list.
• When curr.next is None and the stack is non-empty, pop and reconnect — this resumes the parent-level traversal.
• Always update both next and prev for every new connection — it's a doubly linked list.
• Always clear curr.child = None after inlining the child.
• Time O(n), Space O(d) where d is nesting depth — each node is visited once.
• This is essentially iterative DFS — the same pattern applies to tree traversal, graph traversal, and any hierarchical data structure flattening.