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 singlelevel, doubly linked list. You are given the head of the first level of the list.
Example:
Input:
123456NULL

78910NULL

1112NULL
Output:
123781112910456NULL
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
Comments
Post a Comment