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.
-
flatten([1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]) // should return [1,2,3,7,8,11,12,9,10,4,5,6]
Explanation: The multilevel linked list in the input is as follows: After flattening the multilevel linked list it becomes:
-
flatten([1,2,null,3]) // should return [1,3,2]
Explanation: The input multilevel linked list is as follows:
1---2---NULL | 3---NULL
-
flatten([]) // should return []
We use the multilevel linked list from Example 1 above:
1---2---3---4---5---6--NULL
|
7---8---9---10--NULL
|
11--12--NULL
The serialization of each level is as follows:
[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]
To serialize all levels together we will add nulls in each level to signify no node connects to the upper node of the previous level. The serialization becomes:
[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]
Merging the serialization of each level and removing trailing nulls we obtain:
[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
/**
** Definition for a Node.
* function Node(val,prev,next,child) {
* this.val = val;
* this.prev = prev;
* this.next = next;
* this.child = child;
* };
*/
/**
* @param {Node} head
* @return {Node}
*/
function flatten(head) {
// Loop over the list
for (
let currentNode = head;
currentNode !== null;
currentNode = currentNode.next
) {
// If current node has a child:
if (currentNode.child) {
// Get the tail of the child list
let childTail = currentNode.child;
// Loop over the child list
while (childTail.next !== null) {
childTail = childTail.next;
}
// Point the tail of the child list to the next node
childTail.next = currentNode.next;
// Point the next node's prev pointer
// to the tail of the child list
if (childTail.next) {
childTail.next.prev = childTail;
}
// Point the current node to the head of the child list
currentNode.next = currentNode.child;
// Point the head of the child list's prev pointer
// to the current node
currentNode.child.prev = currentNode;
// Remove the reference to the current node's child
currentNode.child = null;
}
}
// Return the head of the flattened list
return head;
}