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

• Detect Cycle in a Linked List
• Find the first node of a cycle in a linked list
• The Intersection of two linked lists
• Reverse a linked lists
• Rotate a Linked list

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