Code Destine

Problem Statement

You have given a doubly linked list which in addition to the next and previous pointers, it also has 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 given 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.

Example 

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]

Input :- head = [1, 2, 3, null, 4, 5]
Output :- [1, 4, 5, 2, 3]

Solution

We will use a stack data structure to solve this problem. Traverse the given doubly linked list, till the child pointer of a node is null. Once you get a node, whose child pointer is not null push next pointer to stack (if it is not null) and re-link child pointer value to next pointer and child pointer value to null.

Program

import java.util.Stack;

public class Main {

	public static void main(String[] args) {
		
		ListNode head = null;
		
		ListNode node1 = new ListNode();
		node1.value = 1;		
		ListNode node2 = new ListNode();
		node2.value = 2;		
		ListNode node3 = new ListNode();
		node3.value = 3;
		
		head = node1;
		node1.next = node2;
		node2.previous = node1;
		node2.next = node3;
		node3.previous = node2;
		
		ListNode node4 = new ListNode();
		node4.value = 4;		
		ListNode node5 = new ListNode();
		node5.value = 5;
		
		node1.child = node4;
		node4.next = node5;
		node5.previous = node4;
		
		Main main = new Main();
		head = main.flatten(head);
		
		ListNode listNode = head;
		while(listNode != null) {
			System.out.print(listNode.value + ", ");
			listNode = listNode.next;
		}
	}
	
	/* Solution */
	public ListNode flatten(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        
        ListNode node = head, next = null;
        while(node != null){
            
            if(node.child != null){ 
                // setting next to stack
                if(node.next != null){
                    next = node.next;
                    next.previous = null;
                    stack.push(next);  
                }                              
                // setting child to list
                node.next = node.child;
                node.next.previous = node;
                node.child = null;
            }
            
            if(node.next == null && stack.size() > 0){
                next = stack.pop();
                node.next = next;
                next.previous = node;                
            }            
            node = node.next;
        }        
        return head;
    }
	
	/* Definition of Doubly Linked List Node */
	public static class ListNode {
	    int value;
	    ListNode previous;
	    ListNode next;
	    ListNode child;

	    public ListNode() {}

	    public ListNode(int value, ListNode previous, ListNode next, ListNode child) {
	    	this.value = value;
	        this.previous = previous;
	        this.next = next;
	        this.child = child;
	    }
	}	
}

Result

1, 4, 5, 2, 3, 

That’s all for Flatten a Multilevel Doubly Linked List in Java, If you liked it, please share your thoughts in a comments section and share it with others too.