Flatten Linked List

Moderate
0/80
6 upvotes
Asked in companies
DunzoAmazonExpedia Group

Problem statement

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.

example

                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
Detailed explanation ( Input/output format, Notes, Images )
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 :

example
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.
Sample Input 1:
1
1 2 3 4 -1 -1 6 -1 -1 5 -1 -1 -1
Sample Output 1:
1 2 3 4 6 5 -1
Explanation of Sample Input 1:
The given multi-level linked list

example

Flattened linked list

example

Sample Input 2:
1
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
Sample Output 2:
10 5 12 7 11 4 20 13 17 6 2 16 9 8 3 19 15 -1
Explanation of Sample Input 2:
Input tree is as shown in figure 1.
On arranging the input linked list level wise, we get the output as a single-level list.
Hint

Can it be solved using recursion?

Approaches (2)
Recursive approach

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.

  1. Take ‘curr’ pointer, which will point to head of the first level of the list
  2. Take ‘tail’ pointer, which will point to end of the first level of the list
  3. 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.

Time Complexity

O(N), where ‘N’ is the number of nodes present in the Linked List.

Each node is visited at most twice, so the time complexity is O(N+N) = O(2*N) = O(N).

Space Complexity

O(N),  where ‘N’ is the number of nodes in the Linked List

In the worst case, the recursion stack can take O(N) space ( when all the nodes are present on the first level and node has a child ). Thus, the final space complexity is O(N).

Code Solution
(100% EXP penalty)
Flatten Linked List
Full screen
Console