/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;

    public Node() {}

    public Node(int _val,Node _prev,Node _next,Node _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
};
*/
class Solution {
    public Node flatten(Node head) {
        recurse(head);
        return head;
    }

    private Node recurse(Node node) {
        Node prev = node;
        while (node != null) {
            if (node.child == null) {
                prev = node;
                node = node.next;
            } else {
                prev = recurse(node.child);
                prev.next = node.next; // Double linked list, both next and prev should be modified!
                if (prev.next != null) prev.next.prev = prev;
                node.next = node.child;
                node.child.prev = node;
                node.child = null;
                node = prev.next;
            }
        }
        return prev; // Return the last node of flatten list.
    }
}