430. Flatten a Multilevel Doubly Linked List

Link

Solution

The solution is straight-forward.

• Let the child become next, and keep the original next in Stack.

• If the next is null, pop the element from Stack to be the next.

   public Node flatten(Node head) {
        
        Node start = new Node(-1);
        start.next = head;
        Stack<Node> stack = new Stack<>();
        while(head != null){
            if(head.child != null){
                if(head.next != null){
                    stack.push(head.next);
                }
                //child become the next;
                head.next = head.child;
                head.next.prev = head;
                head.child = null;
            }
            if(head.next == null && !stack.isEmpty()){
                //previous next become the curent next
                head.next = stack.pop();
                head.next.prev = head;
            }
            head = head.next;
        }
        return start.next;
    }