Flatten Multilevel Doubly Linked List — DFS Stack

# Python — DFS (recursive)
def flatten(head):
    def dfs(node):
        cur = node
        while cur:
            if cur.child:
                child_head = cur.child
                child_tail = dfs(child_head)
                nxt = cur.next
                cur.next = child_head
                child_head.prev = cur
                child_tail.next = nxt
                if nxt: nxt.prev = child_tail
                cur.child = None
                cur = nxt
            else:
                cur = cur.next
        return child_head if cur is None else cur  # return last node
    if not head: return head
    # Use iterative approach
    stack = []
    cur = head
    while cur:
        if cur.child:
            if cur.next: stack.append(cur.next)
            cur.next = cur.child
            cur.next.prev = cur
            cur.child = None
        if not cur.next and stack:
            nxt = stack.pop()
            cur.next = nxt
            nxt.prev = cur
        cur = cur.next
    return head

// Java — stack
public Node flatten(Node head) {
    if (head == null) return head;
    Deque<Node> stack = new ArrayDeque<>();
    Node cur = head;
    while (cur != null) {
        if (cur.child != null) {
            if (cur.next != null) stack.push(cur.next);
            cur.next = cur.child;
            cur.next.prev = cur;
            cur.child = null;
        }
        if (cur.next == null && !stack.isEmpty()) {
            Node nxt = stack.pop();
            cur.next = nxt; nxt.prev = cur;
        }
        cur = cur.next;
    }
    return head;
}