[LeetCode] 430. Flatten a Multilevel Doubly Linked List

 Problem : https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/

 Use stack to mimic DFS

"""
# 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: 'Node') -> 'Node':
        if not head: return None
        
        dummy = Node()
        p = dummy
        
        stack = [head]
        
        while stack:
            h = stack.pop()
            
            while h:
                p.next = h
                h.prev = p
                p = p.next
                    
                if h.child:
                    if h.next:
                        stack.append(h.next)
                    
                    tmp = h.child
                    h.child = None
                    h = tmp
                else:
                    h = h.next
                
        
        dummy.next.prev = None
        return dummy.next