## Algorithm

Problem Name: 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]
```

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
}
Stack < Node> stack = new Stack<>();
while (!stack.isEmpty()) {
Node removed = stack.pop();
if (removed.next != null) {
stack.push(removed.next);
}
if (removed.child != null) {
stack.push(removed.child);
}
removed.child = null;
if (!stack.isEmpty()) {
removed.next = stack.peek();
stack.peek().prev = removed;
}
}
}
}
``````
Copy The Code &

Input

cmd

Output

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

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const flatten = function (head) {
const handle = (node, next = null) => {
if (!node) return null;
handle(node.next, next);
const child = handle(node.child, node.next);
if (!node.next && next) {
node.next = next;
next.prev = node;
}
if (child) {
node.next = child;
node.child = null;
child.prev = node;
}
return node;
};
};
``````
Copy The Code &

Input

cmd

Output

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

### #3 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
{
{
var dummy = new Node();
var curr = dummy;

FlattenHelper(curr);

return dummy.next;
}

{
while (curr != null)
{
if (curr.child == null)
{
if (curr.next != null)
{
curr = curr.next;
continue;
}
else
break;
}

var next = curr.next;
var nextLevelTail = FlattenHelper(curr.child);
curr.next = curr.child;
curr.child.prev = curr;
curr.child = null;
nextLevelTail.next = next;
if (next != null)
next.prev = nextLevelTail;
}

return curr;
}

public class Node
{
public int val;
public Node prev;
public Node next;
public Node child;
}
}
}
``````
Copy The Code &

Input

cmd