430.md

430 Flatten a Multilevel Doubly Linked List

Description

link

---

Solution

这种题目一看就是经过栈就可以实现搜索，先入next，再入child，就可以实现flat，逻辑很简单，代码如下

---

Code

O(n)

"""
# 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
        
        dummy = Node(0, None, head, None)     
        stack = []
        stack.append(head)
        prev = dummy
        
        while stack:
            root = stack.pop()

            root.prev = prev
            prev.next = root
            
            if root.next:
                stack.append(root.next)
                root.next = None
            if root.child:
                stack.append(root.child)
                root.child = None
            prev = root        
            
        
        dummy.next.prev = None
        return dummy.next