/*
Runtime: 0 ms, faster than 100.00% of Java online submissions for Flatten a Multilevel Doubly Linked List.
Memory Usage: 37.4 MB, less than 85.00% of Java online submissions for Flatten a Multilevel Doubly Linked List.
*/
class Solution {
    public Node flatten(Node head) {
        flatten2(head);
        return head;
    }

    private Node flatten2(Node head) {
        while(head != null && head.child == null && head.next != null) head = head.next;
        if (head == null || head.child == null)  {
            return head;
        }

        Node trailingTail = head.next;

        head.next = head.child;
        head.next.prev = head;
        head.child = null;

        head = flatten2(head);

        head.next = trailingTail;
        if (head.next != null) {
            head.next.prev = head;
        }
        return flatten2(head);
    }
}