### 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 {

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;
}
}
}
```
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 {

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;
}
}
}
}
```

Other Posts You May Like