Flatten a Multilevel Doubly Linked List

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Output: [1,2,3,7,8,11,12,9,10,4,5,6]
Explanation:

The multilevel linked list in the input is as follows:

After flattening the multilevel linked list it becomes:

We have already covered the Doubly Linked List in our previous blog. If you look into the above problem then you will realize that the Doubly linked list class contains three references (next, previous, and child). It is clear in the flatten Doubly Linked list whenever a child exists, It first traverses, and after then next node will traverse. We start traversing the linked list from the head pointer and if some node has a child then store the next reference into some storage and move toward the child node and again do the same. Once the child node's traversing complete then pop the last reference and go once again until the storage is empty and the doubly linked list reaches till the end.

Node start, tail;
Stack<Node> stack = new Stack<>();

public Node flatten(Node head) {
    if (head == null)
        return head;
    Node curr = head;
    while (curr != null) {
        add(curr.val);
        if (curr.child != null) {
            stack.push(curr.next);
            curr = curr.child;
        } else
            curr = curr.next;
        if (curr == null && !stack.isEmpty()) {
            curr = stack.pop();
        }
    }
    return start;
}

public void add(int val) {
    Node node = new Node();
    node.val = val;
    if (start == null) {
        start = tail = node;
    } else {
        tail.next = node;
        node.prev = tail;
        tail = node;
    }
}

In the above code, we are creating a new linked list with an element that consumes O(n) size memory. Can't we flatten a linked list without extra space? Yes, we can do it without creating a new Linked list.

We will follow the same step to flatten a Doubly Linked List.

1) If there's a child then we push the node's next into the stack and move to the child node.

2) If there's a next then we move to the next node.

3) If there is no child and no next node then we check if the stack is holding a node then move with it otherwise terminate the program.

Stack<Node> stack = new Stack<>();
public Node flatten(Node head) {
    if (head == null)
        return head;
    Node curr = head;
    while (curr != null) {
        if (curr.child != null) {
            stack.push(curr.next);
            curr.next = curr.child;
            curr.next.prev = curr;
            curr.child = null;
        } else {
            if (curr.next == null) {
                curr.next = stack.pop();
                curr.next.prev = curr;
            }
            curr = curr.next;
        }
    }
    return head;
}

I hope you are understanding the solution to the given problem. We will come up with a new challenge soon.