We have discussed flattening of a multi-level linked list where nodes have two pointers down and next. In the previous post, we flattened the linked list level-wise. How to flatten a linked list when we always need to process the down pointer before next at every node.
Input:
1 - 2 - 3 - 4
|
7 - 8 - 10 - 12
| | |
9 16 11
| |
14 17 - 18 - 19 - 20
| |
15 - 23 21
|
24
Output:
Linked List to be flattened to
1 - 2 - 7 - 9 - 14 - 15 - 23 - 24 - 8
- 16 - 17 - 18 - 19 - 20 - 21 - 10 -
11 - 12 - 3 - 4
Note: 9 appears before 8 (When we are
at a node, we process down pointer before
right pointer)
Source: Oracle Interview
If we take a closer look, we can notice that this problem is similar to tree to linked list conversion. We recursively flatten a linked list with the following steps:
- If the node is NULL, return NULL.
- Store the next node of the current node (used in step 4).
- Recursively flatten down the list. While flattening, keep track of the last visited node, so that the next list can be linked after it.
- Recursively flatten the next list (we get the next list from the pointer stored in step 2) and attach it after the last visited node.
Below is the implementation of the above idea.
Javascript
<script>// Javascript program to flatten // a multilevel linked list// Node of Multi-level Linked Listclass Node { constructor(val) { this.data = val; this.down = null; this.next = null; }}var last;// Flattens a multi-level linked// list depth wisefunction flattenList(node) { if (node == null) return null; // To keep track of last visited // node // (NOTE: This is ) last = node; // Store next pointer var next = node.next; // If down list exists, process it // first. Add down list as next of // current node if (node.down != null) node.next = flattenList(node.down); // If next exists, add it after the next // of last added node if (next != null) last.next = flattenList(next); return node;}// Utility method to print a linked listfunction printFlattenNodes(head) { var curr = head; while (curr != null) { document.write(curr.data + " "); curr = curr.next; }}// Utility function to create a // new nodefunction push(newData) { var newNode = new Node(newData); newNode.next = null; newNode.down = null; return newNode;}// Driver codevar head = new Node(1);head.next = new Node(2);head.next.next = new Node(3);head.next.next.next = new Node(4);head.next.down = new Node(7);head.next.down.down = new Node(9);head.next.down.down.down = new Node(14);head.next.down.down.down.down = new Node(15);head.next.down.down.down.down.next =new Node(23);head.next.down.down.down.down.next.down = new Node(24);head.next.down.next = new Node(8);head.next.down.next.down = new Node(16);head.next.down.next.down.down = new Node(17);head.next.down.next.down.down.next = new Node(18);head.next.down.next.down.down.next.next = new Node(19);head.next.down.next.down.down.next.next.next = new Node(20);head.next.down.next.down.down.next.next.next.down = new Node(21);head.next.down.next.next = new Node(10);head.next.down.next.next.down = new Node(11);head.next.down.next.next.next = new Node(12);head = flattenList(head);printFlattenNodes(head);// This code is contributed by aashish1995 </script> |
Output:
1 2 7 9 14 15 23 24 8 16 17 18 19 20 21 10 11 12 3 4
Time complexity : O(n)
Space complexity : O(1)
Alternate implementation using the stack data structure
Javascript
<script>function flattenList2(head){ var headcop = head; var save = new Stack(); save.push(head); var prev = null; while (!save.isEmpty()) { var temp = save.pop(); if (temp.next) save.push(temp.next); if (temp.down) save.push(temp.down); if (prev != null) prev.next = temp; prev = temp; } return headcop;}// This code is contributed by aashish1995 </script> |
Please refer complete article on Flatten a multi-level linked list | Set 2 (Depth wise) for more details!
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
