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

考察链表操作以及递归

"""
# 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':

        curr = head
        while curr:
            if curr.child:
                helper(curr)
            curr = curr.next   
        return head

def helper(node):

    if not node: return
    next_node = node.next
    child = node.child
    head = child
    while child.next:
        if child.child:
            helper(child)
        child = child.next

    # insert child list into parent, between node and next_node
    node.next = head
    head.prev = node
    child.next = next_node
    if next_node: # end of list
        next_node.prev = child

    # set child of current node to None
    node.child = None