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

`````` 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]
Explanation: The multilevel linked list in the input is shown.
After flattening the multilevel linked list it becomes:
1 <--> 2 <--> 3 <--> 7 <--> 8 <--> 11 <--> 12 <--> 9 <--> 10 <--> 4 <--> 5 <--> 6
``````

Example 2:

`````` 1 <--> 2
|
3
Output: [1,3,2]
Explanation: The multilevel linked list in the input is shown.
After flattening the multilevel linked list it becomes:
1 <--> 3 <--> 2
``````

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]
``````
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 `````` ``````""" # 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: 'Optional[Node]') -> 'Optional[Node]': if not head: return head stack = [] cur = head while cur or stack: if cur.child: if cur.next: stack.append(cur.next) cur.next = cur.child cur.child.prev = cur cur.child = None elif not cur.next and stack: cur.next = stack.pop() cur.next.prev = cur cur = cur.next return head """ DFS """ class Solution(object): def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]': if not head: return head pseudoHead = Node(None, None, head, None) self.flatten_dfs(pseudoHead, head) pseudoHead.next.prev = None return pseudoHead.next def flatten_dfs( self, prev: 'Optional[Node]', curr: 'Optional[Node]' ) -> 'Optional[Node]': """ return the tail of the flatten list """ if not curr: return prev curr.prev = prev prev.next = curr # the curr.next would be tempered in the recursive function tempNext = curr.next tail = self.flatten_dfs(curr, curr.child) curr.child = None return self.flatten_dfs(tail, tempNext)``````