Problem Statement

You are given a doubly linked list where in addition to the next and prev pointers, each node also has a child pointer that may point to a separate doubly linked list.

These child lists may have one or more levels of children themselves.

Your task is to flatten the list so that all nodes appear in a single-level doubly linked list.

The flattened list should follow a depth-first order traversal.

---

Example

Input:

1---2---3---4---5---6
        |
        7---8---9---10
            |
            11--12

Output:

1---2---3---7---8---11---12---9---10---4---5---6

---

Intuition

This is a linked list problem with recursion or stack-like structure due to nested child pointers.

The idea is to traverse nodes in depth-first order:

1. Visit the current node.
2. If it has a child, flatten the child list recursively.
3. Connect the flattened child list between the current node and the next node.
4. Continue until all nodes are processed.

Essentially, whenever you encounter a child, you insert that list into the main chain.

---

Approach 1: Iterative using Stack

We can use a stack to perform DFS manually without recursion.

Steps:

1. Push the head into a stack.
2. While the stack is not empty:
   • Pop the top node.
   • Connect it to the previous node.
   • If the node has a next, push it to the stack.
   • If the node has a child, push it to the stack.
3. Set all child pointers to null.

This ensures we always go deep first before moving to the next node.

---

Java Solution

import java.util.*;

class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
}

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

        Stack<Node> stack = new Stack<>();
        stack.push(head);
        Node prev = null;

        while (!stack.isEmpty()) {
            Node curr = stack.pop();

            if (prev != null) {
                prev.next = curr;
                curr.prev = prev;
            }

            if (curr.next != null) {
                stack.push(curr.next);
            }

            if (curr.child != null) {
                stack.push(curr.child);
                curr.child = null;
            }

            prev = curr;
        }

        return head;
    }
}

---

Approach 2: Recursive (Depth-First Search)

Alternatively, recursion fits naturally with depth-first traversal.

Recursive idea:

• Flatten the child list first.
• Connect child’s tail to the current node’s next.
• Return the tail of the flattened sublist to connect further up.

---

Complexity Analysis

• Time Complexity: O(N), where N = number of all nodes in all levels.
  Each node is visited once.
• Space Complexity: O(N) due to stack/recursion depth.

---

Dry Run

Let’s simulate the flattening of:

1 - 2 - 3 - 4
        |
        5 - 6

Step-by-step:

Step	Stack	Current Node	Operation	Linked List (Flattened So Far)
1	[1]	Pop 1	Push next(2)	1
2	[2]	Pop 2	Push next(3)	1 → 2
3	[3]	Pop 3	Push next(4), push child(5)	1 → 2 → 3
4	[4,5]	Pop 5	Push next(6)	1 → 2 → 3 → 5
5	[4,6]	Pop 6	No next/child	1 → 2 → 3 → 5 → 6
6	[4]	Pop 4	Done	1 → 2 → 3 → 5 → 6 → 4

Output List:

1 → 2 → 3 → 5 → 6 → 4

All child pointers are now null.

---

Key Insights

1. The stack ensures that we always process child before next, maintaining depth-first traversal order.
2. Setting child = null is important to prevent cycles.
3. This pattern (stack-based DFS flattening) is reusable for problems involving multi-level hierarchies (like nested lists or directories).