Last Updated: 24 Nov, 2020
Flatten Linked List
Moderate
Asked in companies
You are given a Multilevel Linked List of integers, where in addition to the next pointer each node has a child pointer, which may or may not point to a separate 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 below figure. You are given the head of the first level of the list. Flatten the list so that all the nodes appear in a single-level linked list. You need to flatten the list in a way that all nodes at first level should come first, then nodes of the second level, and so on.
FIGURE 1
Input for the above list is:
10 5 12 7 11 -1 4 20 13 -1 -1 -1 17 6 -1 -1 -1 2 -1 16 -1 9 8 -1 -1 -1 3 -1 19 15 -1 -1 -1 -1 -1
Input Format:
The first line of input contains a single integer T, representing the number of test cases or queries to be run.
Then the T test cases follow.
The first line of each test case contains the elements of the multi-level linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.
Note :
-1 in the input is representing NULL.
In the input we begin with all the nodes present at first level then -1 indicates the end of that particular level, next we take the child of first node of level 1 and if the child exists we traverse all of its next nodes and then we check if the second node of level 1 has child and repeat the same process, if the child of any node is NULL we put a -1. The input is taken repeating the same process mentioned above for all levels.
Illustration of above method is shown below :
First Level - 1 2 3 4
Then the first level ends as no further next node is present and the next node for 4 is NULL. So insert a -1 in the input. So the input upto now is
1 2 3 4 -1
Now, we check if the first node of first level has any child or its child is NULL, its NULL so insert -1 in the input and repeat the same process for all the nodes until you have traversed all the nodes of the linked list.
The final input for the list will be: 1 2 3 4 -1 -1 6 -1 -1 5 -1 -1 -1
Output Format:
For each test case, print the sorted linked list. The elements of the sorted list should be single-space separated, terminated by -1.
The output of each test case is printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 5 * 10^4
-10^9 <= data <= 10^9 and data != -1
where T is the number of test cases, L is the number of nodes in the linked list.
Approaches
The problem clearly says that we need to flatten the linked list level by level. The idea of the solution is, we first find the tail of the first level and maintain a pointer which will iterate the linked list’s next nodes. If any node has a child append it to the tail and update the tail to the new last node and recursively repeat the same steps until the tail node is reached.
- Take ‘curr’ pointer, which will point to head of the first level of the list
- Take ‘tail’ pointer, which will point to end of the first level of the list
- The recursive function will have ‘curr’ node, ‘tail’ node as its arguments.
I) Base condition : if current node reaches NULL, return.
II) If current node has a child then
1. Append this new child list to the ‘tail’
tail->next = curr->child
2. Find the last node of new child list and update ‘tail’
tmp = curr->child;
while (temp->next != NULL)
temp = tmp->next;
tail = temp;
III) Move to the next node. i.e. curr = curr->next and call the function again for the updated values of the curr and tail node.
The problem clearly says that we need to flatten the linked list level by level. The idea of the solution is, we start from the first level, process all nodes one by one, if a node has a child, then we append the child at the end of the list, otherwise, we don’t do anything. After the first level is processed, all next-level nodes will be appended after the first level. The same process is followed for the appended nodes.
- Take ‘curr’ pointer, which will point to head of the first level of the list
- Take ‘tail’ pointer, which will point to end of the first level of the list
- Repeat the below procedure while ‘curr’ is not NULL.
I) If current node has a child then
1. Append this new child list to the ‘tail’
tail->next = curr->child
2. Find the last node of new child list and update ‘tail’
tmp = curr->child;
while (temp->next != NULL)
temp = tmp->next;
tail = temp;
II) Move to the next node. i.e. curr = curr->next