430. Flatten a Multilevel Doubly Linked List

"""
Basic idea is straight forward:

1. Start form the head , move one step each time to the next node
2. When meet with a node with child, say node p, follow its child chain to the end and connect the tail node with p.next, by doing this 3. we merged the child chain back to the main thread
4. Return to p and proceed until find next node with child.
5. Repeat until reach null
"""
class Solution:
    def flatten(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if not head:
            return None

        tmp = head
        while tmp:
            # if got a child:
            if tmp.child:
                tmp2 = tmp.child

                # find the tail of the child
                while tmp2.next:
                    tmp2 = tmp2.next

                # link it to tmp.next
                tmp2.next = tmp.next

                # if tmp.next not None, connect the tmp.next.prev to the tail of the children list
                if tmp.next:
                    tmp.next.prev = tmp2

                # connect the children list to ancestor list and None the child
                tmp.next = tmp.child
                tmp.child.prev = tmp
                tmp.child = None

            # if doesn't got child, go to the next
            else:
                tmp = tmp.next

        return head