# Flatten a Multilevel Doubly Linked List
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list)
Canonical: https://scaleengineer.com/dsa/problems/flatten-a-multilevel-doubly-linked-list
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Linked List, Doubly-Linked List
**Companies:** [SoFi](https://scaleengineer.com/companies/sofi), [Arista Networks](https://scaleengineer.com/companies/arista-networks)
---
## Problem
You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional **child pointer**. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a **multilevel data structure** as shown in the example below.

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. The nodes in the list must have **all** of their child pointers set to_ `null`.

**Example 1:**

![](https://assets.glich.co/dsa/flatten-a-multilevel-doubly-linked-list/image0.jpg) 

**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]
**Explanation:** The multilevel linked list in the input is shown.
After flattening the multilevel linked list it becomes:
![](https://assets.glich.co/dsa/flatten-a-multilevel-doubly-linked-list/image1.jpg)

**Example 2:**

![](https://assets.glich.co/dsa/flatten-a-multilevel-doubly-linked-list/image2.1jpg) 

**Input:** head = [1,2,null,3]
**Output:** [1,3,2]
**Explanation:** The multilevel linked list in the input is shown.
After flattening the multilevel linked list it becomes:
![](https://assets.glich.co/dsa/flatten-a-multilevel-doubly-linked-list/image3.jpg)

**Example 3:**

**Input:** head = []
**Output:** []
**Explanation:** There could be empty list in the input.

**Constraints:**

* The number of Nodes will not exceed `1000`.
* `1 <= Node.val <= 105`

**How the multilevel linked list is represented in test cases:**

We use the multilevel linked list from **Example 1** above:

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

The serialization of each level is as follows:

[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]

To serialize all levels together, we will add nulls in each level to signify no node connects to the upper node of the previous level. The serialization becomes:

[1,    2,    3, 4, 5, 6, null]
             |
[null, null, 7,    8, 9, 10, null]
                   |
[            null, 11, 12, null]

Merging the serialization of each level and removing trailing nulls we obtain:

[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

# Approaches
## Recursive Depth-First Search (DFS)
This approach uses recursion to perform a depth-first traversal of the multilevel list. A helper function is designed to flatten a given sublist and return its tail. This allows the parent level to correctly link the flattened child list into place before continuing its own traversal.
**Time:** O(N), where N is the total number of nodes in the list. Each node is visited a constant number of times during the traversal and pointer manipulation. · **Space:** O(D), where D is the maximum depth of the child lists. In the worst-case scenario (a linked list where each node's `next` is null and `child` is not), the recursion depth can be N, leading to O(N) space complexity for the call stack.
**Pros:** The solution is elegant and closely mirrors the recursive definition of the data structure.; The code can be relatively clean and easy to understand for those familiar with recursion.
**Cons:** Can lead to a `StackOverflowError` if the list is very deep (i.e., has many nested child levels).; Recursion can introduce performance overhead compared to an iterative solution.
### Explanation
The core idea is to solve the problem by breaking it down into smaller, identical subproblems, which is a natural fit for recursion. We can define a recursive function that takes the head of a list (or sublist) and flattens it. A key part of the design is that this function must return the *tail* of the flattened list it produces. This is necessary so that the caller, which is processing a higher-level list, knows where to attach the rest of its own list.

The process for a given node `curr` is as follows: if `curr` has a child, we first recursively flatten that child's list. Once that's done and we have the tail of the flattened child list, we can 'splice' this list into the main list. This involves re-wiring the `next` and `prev` pointers of `curr`, the head of the child list, the tail of the child list, and `curr`'s original `next` node. After splicing, we set `curr.child` to `null` as required and continue our traversal from where the spliced list ends.

```java
/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};
*/
class Solution {
    public Node flatten(Node head) {
        if (head == null) {
            return null;
        }
        flattenRec(head);
        return head;
    }

    // Flattens the list starting at 'node' and returns the tail of the flattened list.
    private Node flattenRec(Node node) {
        Node curr = node;
        Node tail = node; // Keep track of the last node visited

        while (curr != null) {
            Node nextNode = curr.next;
            
            if (curr.child != null) {
                // Flatten the child list and get its tail
                Node childTail = flattenRec(curr.child);
                
                // Splice the child list in
                curr.next = curr.child;
                curr.child.prev = curr;
                curr.child = null;
                
                // Connect the child tail to the original next node
                childTail.next = nextNode;
                if (nextNode != null) {
                    nextNode.prev = childTail;
                }
                
                // The new tail of the list processed so far is the child's tail
                tail = childTail;
                // The next node to process is what was originally after the child tail
                curr = nextNode; 
            } else {
                // No child, just move to the next node
                tail = curr;
                curr = nextNode;
            }
        }
        return tail;
    }
}
```
### Algorithm
*   Define a recursive function, let's call it `flattenRec(node)`, which takes a node, flattens the list starting from it, and returns the tail of the flattened list.
*   The main `flatten` function will call this recursive helper on the `head` and return the `head`.
*   Inside `flattenRec(node)`:
    1.  Initialize a `curr` pointer to `node` and a `tail` pointer, also to `node`.
    2.  Iterate while `curr` is not null.
    3.  If `curr` has a `child`:
        a.  Store `curr.next` in a temporary variable, `nextNode`.
        b.  Make a recursive call `flattenRec(curr.child)` to flatten the child sublist. This call returns the tail of the flattened child list, let's call it `childTail`.
        c.  Splice the child list in: set `curr.next` to `curr.child`, `curr.child.prev` to `curr`, and `curr.child` to `null`.
        d.  Connect the end of the newly inserted child list to the rest of the original list: set `childTail.next` to `nextNode`, and if `nextNode` is not null, set `nextNode.prev` to `childTail`.
        e.  Update the overall `tail` of the processed list to be `childTail`.
        f.  Crucially, continue the iteration by setting `curr` to `nextNode`.
    4.  If `curr` has no child, simply update `tail = curr` and move to the next node `curr = curr.next`.
*   After the loop finishes, return the `tail`.

## Iterative DFS with a Stack
This approach simulates the recursive DFS using an explicit stack, thereby avoiding deep recursion issues like stack overflow. It effectively performs a pre-order traversal of the list structure (Node, then Child, then Next) by carefully managing the order of nodes pushed onto the stack.
**Time:** O(N), where N is the total number of nodes. Each node is pushed onto and popped from the stack exactly once. · **Space:** O(N) in the worst case. The stack's size depends on the number of nodes that have a `next` or `child` pointer. In a structure where many nodes have children, the stack can grow up to a size proportional to N.
**Pros:** Avoids recursion, thus preventing stack overflow errors on very deep or large inputs.; Can be more efficient than recursion by avoiding the overhead of function calls.
**Cons:** The logic of pushing `next` then `child` can be slightly less intuitive than a direct recursive approach.; Requires extra space for the stack, which can be significant for certain list structures.
### Explanation
Instead of relying on the call stack for recursion, we can manage the traversal ourselves using an explicit `Stack`. This iterative approach achieves the same DFS traversal pattern. The key is to process nodes in a 'pre-order' fashion: handle the current node, then its entire child branch, and only then the rest of the current level.

To achieve this, when we are at a node `curr`, we push its `next` sibling onto the stack first, followed by its `child`. Since a stack is a Last-In-First-Out (LIFO) data structure, the `child` will be popped and processed before the `next` sibling, which is exactly the behavior we need. We use a `prev` pointer to stitch the nodes together into a single flat list as we pop them from the stack.

```java
/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};
*/
import java.util.Stack;

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

        Node pseudoHead = new Node(0, null, head, null);
        Node prev = pseudoHead;

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

        while (!stack.isEmpty()) {
            Node curr = stack.pop();
            
            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; // Set child to null as required
            }
            prev = curr;
        }
        
        // Detach the pseudo head
        pseudoHead.next.prev = null;
        return pseudoHead.next;
    }
}
```
### Algorithm
*   If the `head` is null, return null.
*   Initialize an empty `Stack` and push the `head` onto it.
*   Create a `pseudoHead` node to simplify pointer linking. Initialize a `prev` pointer to this `pseudoHead`.
*   Loop as long as the stack is not empty:
    1.  Pop a node `curr` from the stack.
    2.  Link `prev` to `curr`: `prev.next = curr` and `curr.prev = prev`.
    3.  Push `curr.next` onto the stack if it's not null. This must be done *before* pushing the child.
    4.  Push `curr.child` onto the stack if it's not null. Because the stack is LIFO (Last-In, First-Out), the child will be processed next.
    5.  Set `curr.child = null` as required.
    6.  Update `prev = curr` for the next iteration.
*   After the loop, the entire list is flattened. Detach the `pseudoHead` and return the original `head` (which is now `pseudoHead.next`).

## Iterative In-Place Flattening (O(1) Space)
This is the most optimal approach in terms of space complexity. It works by iterating through the list and re-wiring the pointers in-place whenever a node with a child is found. It avoids using any extra space proportional to the input size, such as a recursion stack or an explicit stack.
**Time:** O(N), where N is the total number of nodes. Although there's a nested loop to find the tail of child lists, each node in the entire structure is visited only a constant number of times in total. A node is visited by the main `curr` pointer once, and it might be visited again by a `childTail` traversal once. Therefore, the total work is proportional to N. · **Space:** O(1). We only use a few extra pointers (`curr`, `childTail`, `nextNode`) for traversal and temporary storage. This space usage does not depend on the size or structure of the input list.
**Pros:** Extremely space-efficient, using only O(1) constant extra space.; It's an iterative solution, so it's safe from stack overflow errors.
**Cons:** The pointer manipulation logic is more complex and can be harder to debug than the other approaches.; Involves a nested loop to find the tail of each child list, which might seem less efficient at first glance, although the overall complexity remains linear.
### Explanation
The key insight for an O(1) space solution is that we can modify the list directly without needing to store pending nodes elsewhere. We can traverse the list with a pointer `curr`. When we encounter a node with a child, we don't move on. Instead, we 'pause' and integrate the entire child sublist right after `curr`.

To do this, we first need to find the tail of the child sublist. This requires a separate traversal starting from `curr.child`. Once we have this `childTail`, we can perform the surgery: the `childTail` is linked to whatever was originally after `curr` (`curr.next`), and `curr` is linked to its `child`. After all pointers (`next` and `prev`) are correctly updated and `curr.child` is set to `null`, the list is locally flat. We can then simply continue our main traversal from `curr`, which will naturally proceed into the list we just inserted.

```java
/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};
*/
class Solution {
    public Node flatten(Node head) {
        if (head == null) return head;

        Node curr = head;
        while (curr != null) {
            // If there is no child, we just move to the next node
            if (curr.child == null) {
                curr = curr.next;
                continue;
            }

            // If there is a child, find the tail of the child list
            Node childTail = curr.child;
            while (childTail.next != null) {
                childTail = childTail.next;
            }

            // Store the original next node
            Node nextNode = curr.next;

            // Connect the tail of the child list to the original next node
            childTail.next = nextNode;
            if (nextNode != null) {
                nextNode.prev = childTail;
            }

            // Connect the current node to its child list
            curr.next = curr.child;
            curr.child.prev = curr;
            curr.child = null;

            // No need to advance curr in a separate step, the loop's natural
            // progression will handle it. The next node to process is now the
            // head of the former child list.
        }
        return head;
    }
}
```
### Algorithm
*   Start with a pointer `curr` at the `head` of the list.
*   Iterate through the list as long as `curr` is not null.
*   In each iteration, check if `curr.child` exists.
    *   If `curr.child` is `null`, there's nothing to flatten at this node, so just advance `curr` to `curr.next`.
    *   If `curr.child` is not `null`:
        1.  Find the tail of the child sublist. Create a temporary pointer `childTail` starting at `curr.child` and traverse its `next` pointers until you reach the last node.
        2.  Store `curr.next` in a temporary variable, `nextNode`.
        3.  Rewire the pointers to insert the child list: 
            a.  Connect the `childTail` to `nextNode`: `childTail.next = nextNode`.
            b.  If `nextNode` is not null, update its back-pointer: `nextNode.prev = childTail`.
            c.  Connect `curr` to the head of the child list: `curr.next = curr.child`.
            d.  Update the child's back-pointer: `curr.child.prev = curr`.
            e.  Finally, set `curr.child = null`.
*   After handling the child (or if there was no child), advance `curr` to the next node in the now-modified list.
*   Return the original `head`.

# Solutions
### Java

```java
/* // Definition for a Node. class Node { public int val; public Node prev; public Node next; public Node child; }; */ class Solution { public Node flatten ( Node head ) { if ( head == null ) { return null ; } Node dummy = new Node (); dummy . next = head ; preorder ( dummy , head ); dummy . next . prev = null ; return dummy . next ; } private Node preorder ( Node pre , Node cur ) { if ( cur == null ) { return pre ; } cur . prev = pre ; pre . next = cur ; Node t = cur . next ; Node tail = preorder ( cur , cur . child ); cur . child = null ; return preorder ( tail , t ); } }
```

### CPP

```cpp
/* // Definition for a Node. class Node { public: int val; Node* prev; Node* next; Node* child; }; */ class Solution { public: Node * flatten ( Node * head ) { flattenGetTail ( head ); return head ; } Node * flattenGetTail ( Node * head ) { Node * cur = head ; Node * tail = nullptr ; while ( cur ) { Node * next = cur -> next ; if ( cur -> child ) { Node * child = cur -> child ; Node * childTail = flattenGetTail ( cur -> child ); cur -> child = nullptr ; cur -> next = child ; child -> prev = cur ; childTail -> next = next ; if ( next ) next -> prev = childTail ; tail = childTail ; } else { tail = cur ; } cur = next ; } return tail ; } };
```

### Python

```python
""" # Definition for a Node. class Node: def __init__(self, val, prev, next, child): self.val = val self.prev = prev self.next = next self.child = child """ class Solution : def flatten ( self , head : 'Node' ) -> 'Node' : def preorder ( pre , cur ): if cur is None : return pre cur . prev = pre pre . next = cur t = cur . next tail = preorder ( cur , cur . child ) cur . child = None return preorder ( tail , t ) if head is None : return None dummy = Node ( 0 , None , head , None ) preorder ( dummy , head ) dummy . next . prev = None return dummy . next
```