430. Flatten a Multilevel Doubly Linked List

Version #1 DFS
96.57 %
class Solution {
    public Node flatten(Node head) {
        if (head != null) {
            flattenHelper(head);
        }
       
        return head;
    }
   
    // return last node after flatten
    private Node flattenHelper(Node node) {
        if (node.child == null && node.next == null) return node;
        Node childNode = node.child;
        node.child = null;
        Node nextNode = node.next;
        Node childTail = null;
        Node nextTail = null;
        if (childNode != null) {
            childTail = flattenHelper(childNode);
            node.next = childNode;
            childNode.prev = node;
        }
       
        if (nextNode != null) {
            nextTail = flattenHelper(nextNode);
            if (childTail != null) {
                childTail.next = nextNode;
                nextNode.prev = childTail;
            }
        }
        if (nextTail != null) return nextTail;
        else return childTail;
    }
}

Version #2 Stack

75.11 %
class Solution {
    public Node flatten(Node head) {
        Stack<Node> stack = new Stack<>();
        if (head != null) {
            stack.push(head);
        }
        Node curr = null;
        Node prev = null;
        while (!stack.isEmpty()) {
            curr = stack.pop();
            if (curr.next != null) {
                stack.push(curr.next);
            }
            if (curr.child != null) {
                stack.push(curr.child);
            }
            if (curr.prev != prev && prev != null) {
                prev.next = curr;
                curr.prev = prev;
            }
            prev = curr;
            curr.child = null;
        }
        return head;
    }
}