// Runtime: 0 ms, faster than 100.00% of Java online submissions for Flatten a Multilevel Doubly Linked List.
class Solution {
    public Node flatten(Node head) {
        if (head != null) flatten(head, null);
        return head;
    }

    private void flatten(Node head, Node rest) {
        Node c = head;
        Node tail = null;

        while (c != null && c.child == null) {
            tail = c;
            c = c.next;
        }

        if (c == null) {
            link(tail, rest);
            return;
        }

        if (c.next != null) {
            flatten(c.next, rest);
            rest = c.next;
        }

        flatten(c.child, rest);
        link(c, c.child);
        c.child = null;
    }

    private void link(Node node, Node next) {
        node.next = next;
        if (next != null) next.prev = node;
    }
}