Flatten a Multilevel Doubly Linked List

Flattening a multilevel doubly linked list pops up in real‑world scenarios like expanding nested comment threads or unfolding embedded menus. It tests your ability to traverse complex pointer structures, manage additional children chains, and maintain in‑place modifications.

Problem Statement

You’re given the head of a multilevel doubly linked list. Each node has next, prev, and an optional child pointer to another list. Flatten the list so that all nodes appear in a single‑level doubly linked list, using the original next pointers to sequence them, and return the head of the flattened list.

class Node {
    int val;
    Node prev;
    Node next;
    Node child;
    Node(int x) { val = x; prev = next = child = null; }
}

// Signature in an interview:
public Node flatten(Node head);

1. Clarify Requirements Before Jumping Into Code

I’ll verify a few things up front

• An empty head returns null.

• Child lists can themselves have children to arbitrary depth.

• After flattening, all child pointers should be null.

• We should not allocate new nodes—just rewire existing pointers.

• Ordering of the children and parents does not matter

• Aim for O(n) time, extra stack memory is acceptable but no new list.

2. Identify the Category of the Question

This is a pointer‑manipulation on linked structures problem. Common patterns include:

• Depth‑first traversal (recursive or iterative via stack)

• In‑place node insertion and pointer rewiring

• Maintaining a work stack or recursion stack for backtracking

• Two‑pointer sequencing for merging lists

Recognizing a multilevel list flattening often points to DFS or stack‑based traversal.

3. Consider a Brute‑Force Approach to Understand the Problem

Naively, I could collect all nodes in DFS order into an array, then rebuild a single doubly linked list by iterating that array and resetting next/prev.

• Time: O(n) to collect + O(n) to rebuild = O(n)

• Space: O(n) extra list

• Drawback: Uses O(n) auxiliary storage and rebuilds pointers from scratch.

4. Brainstorm More Solutions

To avoid O(n) extra space, I can:

• Recursive DFS in-place:Recurse into each child, flatten that sublist, splice it between the node and its next, then recurse on remainder. It uses O(d) stack for depth d.

• Iterative with explicit stack:Walk the list from head. Whenever a node has a child, push its next onto a stack, rewire child into next, clear child, and continue. When next becomes null, pop from stack and continue. This splices all sublists inline.

• Two-pass insertion:First pass: find all child heads, append them to tail in order. Second pass: relink by scanning. That’s complex pointer logic and risks misordering.

Iteratively weaving children with a stack gives O(n) time, O(n) worst‑case stack, and rewires in one pass. To derive it live, I think about exactly where sublists connect back: if I push the original next onto a stack, I can dive into the child list; when the child end arrives, popping returns me to the parent’s next. That simulates DFS with minimal code.

5. Discuss Trade‑Offs Between Your Solutions

Approach	Time	Space	Pros	Cons
Array + rebuild	O(n)	O(n)	Simple collection and rebuild logic	Extra O(n) memory, rebuild cost
Recursive DFS splice	O(n)	O(d) stack	Clean recursion mirrors list depth	Risk of stack overflow
Iterative with stack	O(n)	O(n) stack	One‑pass, in‑place, explicit control	Needs careful stack management
Two‑pass tail insertion	O(n²)	O(1)	In‑place without stacks	Quadratic in chaining children

Iterative stack approach balances clarity, in‑place rewiring, and linear time.

6. Write Pseudocode to Structure Your Thoughts

function flatten(head):
  if head is null: return null
  stack = empty stack
  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 and stack not empty:
      nextNode = stack.pop()
      curr.next = nextNode
      nextNode.prev = curr

    curr = curr.next

  return head

7. Consider Edge Cases

• Empty list → returns null

• Single node without child → unchanged

• Single node with child chain → child chain inlined

• Multiple siblings with children → children flattened in correct order

• Deeply nested children → stack handles arbitrary depth

8. Write Full Code Syntax

import java.util.Deque;
import java.util.LinkedList;

class Node {
    int val;
    Node prev;
    Node next;
    Node child;
    Node(int x) { val = x; prev = next = child = null; }
}

public class Solution {
    public Node flatten(Node head) {
        if (head == null) return null;

        Deque<Node> stack = new LinkedList<>();
        Node 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.isEmpty()) {
                Node nextNode = stack.pop();
                curr.next = nextNode;
                nextNode.prev = curr;
            }

            curr = curr.next;
        }

        return head;
    }
}

9. Test Your Code

public static void main(String[] args) {
    Solution sol = new Solution();

    // Helper to link nodes omitted for brevity

    // Test 1: empty
    assert sol.flatten(null) == null;

    // Test 2: single-level list only
    Node a1 = buildList(1,2,3);
    Node f1 = sol.flatten(a1);
    assert toArray(f1).equals("[1,2,3]");

    // Test 3: one child at node 2
    Node b1 = buildList(1,2,3);
    Node c1 = buildList(4,5);
    b1.next.child = c1;
    assert toArray(sol.flatten(b1)).equals("[1,2,4,5,3]");

    // Test 4: nested child at 5→child
    Node d1 = buildList(1,2,3);
    Node e1 = buildList(4,5);
    Node g1 = buildList(6);
    d1.next.child = e1;
    e1.next.child = g1;
    assert toArray(sol.flatten(d1)).equals("[1,2,4,5,6,3]");

    // Test 5: multiple children at different levels
    Node h1 = buildList(1,2,3,4);
    Node c2 = buildList(5);
    Node c3 = buildList(6,7);
    h1.child = c2;
    h1.next.child = c3;
    assert toArray(sol.flatten(h1)).equals("[1,5,2,6,7,3,4]");

    System.out.println("All tests passed!");
}

10. Key Lessons to Remember for Future Questions

• Weave and unwind with an explicit stack simulates DFS without recursion.

• Always clear child pointers after splicing to avoid cycles.

• Edge cases—empty, single-node, various nesting—ensure robustness.

• Helper pseudocode that separates stacking, splicing, and unwinding clarifies implementation.

• Discussing brute‑force, recursion, and iterative-stack shows breadth before settling on an optimal approach.

• In-place rewiring patterns extend to trees, graphs, and multi-pointer structures.

• Code cleanliness matters! You could theoretically make the argument that another solution might be better despite being less optimal in terms of time and space.

Good Luck and Happy Coding!