// Runtime: 0 ms, faster than 100.00% of Java online submissions for Flatten a Multilevel Doubly Linked List.
// Memory Usage: 36.6 MB, less than 100.00% of Java online submissions for Flatten a Multilevel Doubly Linked List.

class Solution {
    public Node flatten(Node head) {
        if (head == null) {
            return head;
        }

        Node tmp = head;
        Node oldNext = null;
        while (tmp != null || oldNext != null) {
            if (oldNext != null) {
                tmp.next = oldNext;
                tmp.next.prev = tmp;
                oldNext = null;
            } else if (tmp.child != null) {
                oldNext = tmp.next;
                tmp.next = flatten(tmp.child);
                tmp.next.prev = tmp;
                tmp.child = null;
                while (tmp.next != null) {
                    // tmp.next.prev = tmp;
                    tmp = tmp.next;
                }

            } else {
                // if (tmp.next != null) {
                //     tmp.next.prev = tmp;
                // }
                tmp = tmp.next;
            }
        }
        return head;
    }
}