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

        while (current != null) {
            if (current.child != null) {
                Node last = current.next;
                Node next = flatten(current.child);
                current.next = next;
                next.prev = current;
                current.child = null;

                while(current.next != null) {
                    current = current.next;
                }

                if (last != null) {
                    current.next = last;
                    last.prev = current;
                }
            }
            current = current.next;
        }

        return head;
    }
}