Flatten a Multilevel Doubly Linked List Solution(Java) - The Coding Shala

Home >> Interview Questions >> Flatten a Multilevel Doubly Linked List

Flatten a Multilevel Doubly Linked List Solution

In this post, you will learn how to flatten a multilevel doubly linked list in Java.

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.

Example:
Input:

 1---2---3---4---5---6--NULL

         |

         7---8---9---10--NULL

               |

              11--12--NULL

Output:

1-2-3-7-8-11-12-9-10-4-5-6-NULL

Flatten a multilevel doubly linked list Java solution

Approach 1:
We can do this using recursion. Whenever the child is not empty, traverse using the child node and do linking next, prev and make child node as null.
Java Program: 

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;

    public Node() {}

    public Node(int _val,Node _prev,Node _next,Node _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
};
*/
class Solution {
    public Node flatten(Node head) {
        if(head == null) return null;
        Node current = head;
        
        while(current != null){
            if(current.child != null){
                Node nextNode = current.next;
                Node childNode = flatten(current.child); //get recursive child
                
                current.child = null;
                current.next = childNode;
                childNode.prev = current;
                
                while(current.next != null) current = current.next;
                current.next = nextNode;
                
                if(nextNode != null) nextNode.prev = current;
            }
            current = current.next;
        }
        return head;
    }
}
Approach 2:
Iterative solution.
Java Program: 

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;

    public Node() {}

    public Node(int _val,Node _prev,Node _next,Node _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
};
*/
class Solution {
    public Node flatten(Node head) {
        if(head == null) return null;
        Node current = head;
        
        while(current != null){
            if(current.child == null) current = current.next;
            else{
                Node nextNode = current.next;
                Node childNode = current.child;
                
                current.child = null;
                current.next = childNode;
                childNode.prev = current;
                
                while(childNode.next != null) childNode = childNode.next;
                childNode.next = nextNode;
                
                if(nextNode != null) nextNode.prev =  childNode;
            }
        }
        return head;
    }
}


Other Posts You May Like
Please leave a comment below if you like this post or found some error, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

New Year Chaos Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala