Last Updated: 29 Jan, 2021
Flatten A Linked List
Easy
Asked in companies
You are given a linked list containing 'n' 'head' nodes, where every node in the linked list contains two pointers:
(1) ‘next’ which points to the next node in the list
(2) ‘child’ pointer to a linked list where the current node is the head.
Each of these child linked lists is in sorted order and connected by 'child' pointer.
Your task is to flatten this linked such that all nodes appear in a single layer or level in a 'sorted order'.
Example:
Input: Given linked list is:
Output:
1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 12 → 20 → null.
Explanation:
The returned linked list should be in a sorted order. All the elements in this returned linked list are connected by 'child' pointers and 'next' pointers point to null.
Input format :
The first line of the input contains a single integer ‘n’ which represents the number of head nodes in the linked list.
The next '2n' lines represent 'n' linked lists connected by next pointer at the head. Description of each of these linked lists is as follows:
The first line contains a single integer 'k', number of nodes in the current linked list.
The next line contains 'k' spaced integers, representing elements of the linked list.
Output format :
Return the head node of the final linked list.
Note:
You don’t have to print anything, it has already been taken care of. Just implement the given function. The flattened list will be printed using the child pointer.
Approaches
The idea is to use an extra array to first store all the elements of the linked list and then sort the array and finally put those elements back into the linked list and return.
- Declare an array ‘Answer’ to store the elements of the linked list.
- Run a while loop till the next of the linked list reaches NULL.
- Add the current pointer data to Answer.
- Inside this loop, traverse the CHILD nodes of the current node.In every iteration of this loop add the data of every node to Answer.
- After this loop, move to the next node of the current node..
- After these loops sort the array and add the array elements to the new linked list and return it.
The idea is to use the given situation that each sublist is sorted and there are a total of N nodes that means there are N sorted sublists. So the idea is to sort the whole thing.
- First of all, we need to add the nodes that are on the first horizontal level that are heads of the sublist to the priority queue say pq.
- Now run a while loop until this queue goes empty.
- Now take out the smallest element from the priority queue that is just pop the element from the priority queue.
- Insert the next child node pointed by the current node (if the child node is not null).
- And repeat these above two steps until the queue goes empty.
- Now add the popped nodes to the linked list.
- Here we will not create new nodes for making the list instead we just change the links i.e. we will make a new node headOne and initially we will make it equal to the first popped node.
- After that, we will keep on adding the nodes by changing the links.
- Finally, return the linked list obtained.
The idea is to merge the linked list in place and merge it recursively with the current flattened list. Basically, we are traversing through the linked list and each time, we are merging the two-child lists into one. We will repeat this process until we are left with only one final linked list containing all the nodes. In short, we repeatedly merge the current list with the already flattened list.
- Make a function mergeLists which will take two lists as parameters.
- Basically, this function is merging two sorted lists as we do in merge sort of linked list.
- Inside this function check for the null nodes i.e. if the first list is empty then return the second list else return the first list.
- Now compare the data of both the list if the data of first st list is lesser than second then recurse on the child of first
- Else recurse on the child of the second list.
- Finally, return the node.
- Now in the flattenLinkedList function here also recurse on the next pointer of the list and after that call the 'mergeList' functions (to merge the current flattened linked list with already flattened one) and finally return head.