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:**

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:

**Example 2:**

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:

**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 <= 10`

^{5}

**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]

### Problem Explanation

The goal is to flatten a multilevel doubly linked list. Each node has `next`

, `prev`

, and `child`

pointers. The `child`

pointer points to another doubly linked list, which might have its own `child`

pointers. We need to flatten this structure into a single-level doubly linked list.

### Approach

- Traverse the linked list using a pointer
`current`

. - Whenever we encounter a node with a
`child`

, we need to:- Temporarily store the
`next`

node. - Flatten the
`child`

list recursively. - Insert the flattened
`child`

list between the current node and the next node. - Update all the necessary pointers (
`next`

and`prev`

). - Ensure the
`child`

pointer is set to`null`

.

- Temporarily store the
- Continue this process until the entire list is flattened.

Code with Detailed Comments

```
var flatten = function(head) {
if (head === null) return null;
// Start traversing from the head node
let current = head;
// Traverse the entire linked list
while (current !== null) {
// If the current node has a child, we need to flatten it
if (current.child !== null) {
// Store the next node temporarily
let next = current.next;
// Recursively flatten the child list
let child = flatten(current.child);
// Insert the flattened child list
current.next = child;
child.prev = current;
// Find the tail of the flattened child list
while (child.next !== null) {
child = child.next;
}
// Connect the tail of the flattened child list to the next node
if (next !== null) {
next.prev = child;
}
child.next = next;
// Remove the child pointer
current.child = null;
}
// Move to the next node
current = current.next;
}
return head;
};
```

### Step-by-Step Explanation

**Initialization**:- Check if
`head`

is`null`

. If it is, return`null`

immediately. - Initialize
`current`

to start from the`head`

node.

- Check if
**Traversal**:- Use a
`while`

loop to traverse the entire linked list.

- Use a
**Handling the**:`child`

- If
`current`

has a`child`

, perform the following steps:- Temporarily store the
`next`

node (`current.next`

). - Recursively flatten the
`child`

list by calling`flatten(current.child)`

. - Insert the flattened
`child`

list between the`current`

node and the`next`

node:- Set
`current.next`

to the head of the flattened`child`

list. - Update the
`prev`

pointer of the flattened`child`

list head to point to`current`

.

- Set
- Find the tail of the flattened
`child`

list by iterating through it until`child.next`

is`null`

. - Connect the tail of the flattened
`child`

list to the`next`

node:- Set
`next.prev`

to the tail of the flattened`child`

list (if`next`

is not`null`

). - Set the
`next`

pointer of the tail of the flattened`child`

list to`next`

.

- Set
- Set
`current.child`

to`null`

as it is now flattened and integrated into the main list.

- Temporarily store the

- If
**Continue Traversal**:- Move
`current`

to the next node (`current.next`

) and repeat the process until the end of the list is reached.

- Move

### Complexity Analysis

**Time Complexity**: O(n), where n is the total number of nodes in the list. Each node is processed once, and the child lists are flattened and inserted in linear time.**Space Complexity**: O(d), where d is the maximum depth of the multilevel list. This space is used by the recursion stack due to the depth-first search approach.

This approach ensures that all pointers are correctly updated, maintaining the doubly linked structure while flattening the multilevel list into a single-level list.