Last Updated: 17 Dec, 2020
Sort Biotonic DLL
Moderate
Asked in company
Sort the given biotonic doubly linked list.
Note :
Biotonic Doubly linked list is the one which is first increasing and then decreasing. A strictly increasing or strictly decreasing doubly linked list is also biotonic.
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 and the only line of every test case contains the elements of the doubly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.
Output Format :
For each test case, print the sorted doubly linked list.
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, N is the length of the doubly linked list.
Time Limit : 1sec
Approaches
The main idea is to store the values of all nodes in a list and then sort that list. After that create a doubly-linked list of N size where N is the size of the list and the value of ith node from left is ith value in a list from i equal to 1 to N.
We will use the ‘Merge Sort’ algorithm to sort the given doubly linked list. Merge Sort is a Divide and Conquer algorithm. In this algorithm, we will divide the list into two parts, recursively sort the two parts and finally merge them such that the resultant list will be sorted.
Algorithm:
- If the list contains only one node, return the head of the list.
- Else, divide the list into two sublists. For this, we will take pointers ‘mid’ and ‘tail’ which will initially point to the head node. We will change ‘mid’ and ‘tail’ as follows until ‘tail’ becomes NULL:
mid = mid->next
tail = tail->next->next
The above operation will ensure that mid will point to the middle node of the list. ‘mid’ will be the head of the second sublist, so we will change the ‘next’ value of the node which is before mid to NULL.
- Call the same algorithm for the two sublists.
- Merge the two sublists and return the head of the merged list. For this, we will take a pointer to node , ‘mergeList’, which will be initially pointing to NULL. If the head of the first sublist has a value less than the head of the second sublist then we will point the ‘mergeList’ to the head of the first sublist and change the head to its next value. Else, we will point the ‘mergeList’ to the head of the second sub list. Since the list is a doubly linked list we will also point the nodes to their respective previous nodes in the mergeList. In the end, if any of the sublists becomes empty and the other sublist is non-empty, then we will add all nodes of the non-empty sublist in the ‘mergeList’.
One way is to find the first node in the doubly linked list which is smaller than its previous node and let it be current. If no such node is present then the list is already sorted.
Split the list into two parts, one from head to node just before the current node and another from current node to the end node.Then reverse the second sub-list starting from current node to the end. Now merge these two sorted lists and return the merged list.
Algorithm:
- Find the first node whose value is less than its previous node.
- Split the list at the current node and reverse the second list (starting from the current node and ending at the last node).
- Merge the two sorted linked lists.
- Return the head of the merged lists.
The idea is to take two pointers, one pointing at the head node of the list and another pointing at the last node of the list. Now compare the values of these two nodes and add the smaller node to the result list. Then advance the pointer of the smaller node. Repeat the above process until all the nodes of the list are processed.
Algorithm:
- Take two pointers, front and last and point them to the first and last node of the linked list respectively.
- Compare the value of two nodes and add the smaller one to the result list.
- Advance either the front or the last pointer accordingly and repeat this process until all the nodes of the linked list are processed.
- Return the head of the result list.