###### tags: `Leetcode` `medium` `list` `python`

# 430. Flatten a Multilevel Doubly Linked List

## [題目連結:] https://leetcode.com/problems/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 3:**

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

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

#### [圖片來源:] https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/

## 解題想法:
* 題目為: 給一個double link list 的結構，要求坦平:
* child連的List併到當前curr同一列
* 想法:
* 設dummy輔助,dummy.next=head
* 用stack:
* 每次pop()最右邊新加入的
* 若有cur.next，將其加入stack
* 若有cur.child，將其加入
* 須將cur.child改為None
* 重新連double link

## Python:

class Node(object):
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
    def insertNext(self,node):
        if not self.next:
            self.next=Node(node,self,None,None)
        else:
            self.next.insertNext(node)
    def printList(self):
        head=self
        res=[]
        while head:
            res.append(head.val)
            head=head.next
        print(res)
            
class Solution(object):
    def flatten(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if not head:
            return head
        dummy=Node(0,None,head,None)
        pre=dummy
        stack=[head]
        while stack:
            cur=stack.pop() #後進先出
            if cur.next:
                stack.append(cur.next)
            if cur.child:
                stack.append(cur.child)
                cur.child=None #要平等 沒有子了
            pre.next=cur
            cur.prev=pre
            pre=pre.next
        #head不能指回自己設的dummy
        dummy.next.prev=None
        return dummy.next

if __name__ == '__main__':
    
    List1=Node(1,None,None,None)
    List1.insertNext(2)
    List1.insertNext(3)
    List1.insertNext(4)
    List1.insertNext(5)
    List1.insertNext(6)
    List1.printList()

    List2=Node(7,None,None,None)
    List2.insertNext(8)
    List2.insertNext(9)
    List2.insertNext(10)
    List2.printList()

    List3=Node(11,None,None,None)
    List3.insertNext(12)
    List3.printList()

    #combined
    List1.next.next.child=List2
    List2.next.child=List3

    result=Solution()
    ans=result.flatten(List1)
    ans.printList()