430. 扁平化多级双向链表

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

解法一：dfs

dfs遍历链表，遇到有孩子的节点i就递归其子链，并将其子链插入i之后

"""
# 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':
        self.dfs(head)
        return head
    
    def dfs(self, head):
        i = head
        pre = None
        while i:
            if i.child:
                childLast = self.dfs(i.child)   #对子链递归，返回子链尾
                
                #子链末尾与i后继街上
                childLast.next = i.next
                if i.next:  #若i后继不为空，修改后继的前驱
                    i.next.prev = childLast                
                    
                #i后继改为子链头
                i.next = i.child
                i.child.prev = i
                #i子项置空
                i.child = None
                #跳过子链
                i = childLast
            pre = i
            i = i.next
        return pre  #本级返回链尾