# 430. Flatten a Multilevel Doubly Linked List

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 <= 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]
```

### 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

1. Traverse the linked list using a pointer `current`.
2. 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`.
3. Continue this process until the entire list is flattened.

``````var flatten = function(head) {
if (head === null) return null;

// Start traversing from the head node

// 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;
}

};
``````

### Step-by-Step Explanation

1. Initialization:
• Check if `head` is `null`. If it is, return `null` immediately.
• Initialize `current` to start from the `head` node.
2. Traversal:
• Use a `while` loop to traverse the entire linked list.
3. 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`.
• 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 `current.child` to `null` as it is now flattened and integrated into the main list.
4. Continue Traversal:
• Move `current` to the next node (`current.next`) and repeat the process until the end of the list is reached.

### 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.

This site uses Akismet to reduce spam. Learn how your comment data is processed.