# LeetCode Medium 430. Flatten a Multilevel Doubly Linked List

tags: leetcode

問題

• Explore
• Problems

アイデア

｢前後ポインタだけでなく，子リストへのポインタも持つ連結リストが与えられる．この複数層連結リストを単層化しろ｣という問題です．

与えられる連結リストのheadは最も上の層のもので，DFSをしろということです．DFSならばあるデータ構造を使うのが楽ですね．

解法

• 次にたどるノードをスタックで管理します．
  • これによってDFSをが可能になります．
• next，child があればスタックに積みます．
  • nextを先に積むことで，後で積まれたchildノードから探索されます．

計算量

ノードの数を$N$をとする．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(N)$

Python

"""
# 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
        
        stk = [head]
        prev = Node(0)
        while stk:
            cur = stk.pop()
            cur.prev = prev
            prev.next = cur
            prev = cur
            if cur.next:
                stk.append(cur.next)
            if cur.child:
                stk.append(cur.child)
                cur.child = None
                
        head.prev = None
        return head