Flatten a Multilevel Doubly Linked List

medium linked list dfs doubly linked list

Problem

Flatten a doubly linked list where each node has next, prev, and an optional child pointer into a single-level doubly linked list. Children are spliced in immediately after their parent. All child pointers are nulled out.

Input1 ↔ 2 ↔ 3; 2.child → 4 ↔ 5

Output1 ↔ 2 ↔ 4 ↔ 5 ↔ 3

Walk DFS-style: emit each node, dive into child before continuing along next.

spine | children (e.g. "1,2,3 | 2:4,5")

def flatten(head):
    if not head: return None
    stack, prev = [head], None
    while stack:
        cur = stack.pop()
        if prev:
            prev.next = cur
            cur.prev = prev
        if cur.next: stack.append(cur.next)
        if cur.child:
            stack.append(cur.child)
            cur.child = None
        prev = cur
    return head

function flatten(head) {
  if (!head) return null;
  const stack = [head];
  let prev = null;
  while (stack.length) {
    const cur = stack.pop();
    if (prev) { prev.next = cur; cur.prev = prev; }
    if (cur.next) stack.push(cur.next);
    if (cur.child) { stack.push(cur.child); cur.child = null; }
    prev = cur;
  }
  return head;
}

class Solution {
    public Node flatten(Node head) {
        if (head == null) return null;
        Deque<Node> stack = new ArrayDeque<>();
        stack.push(head);
        Node prev = null;
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            if (prev != null) { prev.next = cur; cur.prev = prev; }
            if (cur.next != null) stack.push(cur.next);
            if (cur.child != null) { stack.push(cur.child); cur.child = null; }
            prev = cur;
        }
        return head;
    }
}

Node* flatten(Node* head) {
    if (!head) return nullptr;
    stack<Node*> st;
    st.push(head);
    Node* prev = nullptr;
    while (!st.empty()) {
        Node* cur = st.top(); st.pop();
        if (prev) { prev->next = cur; cur->prev = prev; }
        if (cur->next) st.push(cur->next);
        if (cur->child) { st.push(cur->child); cur->child = nullptr; }
        prev = cur;
    }
    return head;
}

Explanation

Each node here can branch downward through a child pointer, forming a tree-like list. We need to "flatten" it into one flat doubly linked chain where, whenever a node has a child, that whole child chain is spliced in right after the node and before its original next.

That "go into the child first, then come back to next" order is exactly depth-first traversal. This solution does the DFS iteratively using an explicit stack instead of recursion, which avoids deep call stacks.

The trick is the push order. For each node we pop, we first push its next, then push its child. Because a stack is last-in-first-out, the child gets popped before next — so the child chain is visited and stitched in first. As we pop each node we link it to the previously emitted node with prev.next = cur and cur.prev = prev, and we clear cur.child = None so no child pointers remain.

Example: spine 1 ↔ 2 ↔ 3 where 2 has child 4 ↔ 5. We pop 1, push nothing extra; pop 2, push 3 then push 4; pop 4 (child wins), push 5; pop 5; pop 3. The emit order is 1, 2, 4, 5, 3.

The result is 1 ↔ 2 ↔ 4 ↔ 5 ↔ 3, exactly the flattened list. Every node is visited once, so it is linear time.

Time: O(n) Space: O(n)