Flattening a Multilevel Linked List into a Single Level
Extracting Elements:
Initially, all elements from the multilevel linked list were extracted and collected, traversing both next and bottom pointers to compile a comprehensive list of values.
BST Construction:
To ensure the flattened list is sorted, the collected values were then used to construct a Binary Search Tree (BST). This step leverages the BST's inherent sorting capability, arranging the elements in ascending order through in-order traversal.
LinkedList Reconstruction:
Finally, the sorted elements from the BST were used to construct a new, single-level linked list. This reconstructed list contains all original elements, now sorted and accessible via the bottom pointer, effectively achieving a flattened structure.
1class Node {
2 constructor(value) {
3 this.value = value;
4 this.next = null;
5 this.bottom = null;
6 }
7}
8
9function newNode(value) {
10 return new Node(value);
11}
12
13function constructLinkedList() {
14 let head = newNode(5);
15 head.bottom = newNode(7);
16 head.bottom.bottom = newNode(8);
17 head.bottom.bottom.bottom = newNode(30);
18
19 head.next = newNode(10);
20 head.next.bottom = newNode(20);
21
22 head.next.next = newNode(19);
23 head.next.next.bottom = newNode(22);
24 head.next.next.bottom.bottom = newNode(50);
25
26 head.next.next.next = newNode(28);
27 head.next.next.next.bottom = newNode(35);
28 head.next.next.next.bottom.bottom = newNode(40);
29 head.next.next.next.bottom.bottom.bottom = newNode(45);
30
31 return head;
32}
33
34const head = constructLinkedList();
35
36function printList(head) {
37 let element = [];
38 let current = head;
39 while (current != null) {
40 element.push(current.value);
41 let bottom = current.bottom;
42 while (bottom != null) {
43 element.push(bottom.value);
44 bottom = bottom.bottom;
45 }
46 current = current.next;
47 }
48 return element;
49}
50
51class BSTNode {
52 constructor(val) {
53 this.data = val;
54 this.left = null;
55 this.right = null;
56 }
57}
58class BST {
59 constructor() {
60 this.root = null;
61 }
62 insert(val) {
63 const newNode = new BSTNode(val);
64 if (!this.root) {
65 this.root = newNode;
66 return;
67 }
68 let current = this.root;
69 while (current) {
70 if (val < current.data) {
71 if (!current.left) {
72 current.left = newNode;
73 return;
74 }
75 current = current.left;
76 } else if (val > current.data) {
77 if (!current.right) {
78 current.right = newNode;
79 return;
80 }
81 current = current.right;
82 } else {
83 return;
84 }
85 }
86 }
87 printInOrder(node = this.root) {
88 if (!node) return [];
89 return [...this.printInOrder(node.left), node.data, ...this.printInOrder(node.right)];
90 }
91}
92function createBSTFromList(head) {
93 let bst = new BST();
94 let arr = printList(head);
95 for (let i = 0; i < arr.length; i++) {
96 bst.insert(arr[i]);
97 }
98 let arrSorted = bst.printInOrder();
99
100 return arrSorted;
101}
102
103function createLinkedListFromArray(arr) {
104 if (arr.length === 0) {
105 return null;
106 }
107 let head = newNode(arr[0]);
108 let current = head;
109 for (let i = 1; i < arr.length; i++) {
110 current.bottom = newNode(arr[i]);
111 current = current.bottom;
112 }
113
114 return head;
115}
116
117console.log(printList(createLinkedListFromArray(createBSTFromList(head))));
118//TC - worst case O(N*N) ideal case O(NlogN)
119