Last Updated: 6 Jan, 2021
QuickSort On Doubly Linked List
Hard
Asked in company
You are given the head of Doubly Linked List containing ‘N’ nodes. Each node will have an integer value stored in it. You need to return the head of the Doubly linked list after sorting it using the QuickSort algorithm.
For example :
Input Format :
The first line of the input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains a single positive integer ‘N’ denoting the number of the element nodes present in the doubly linked list.
The second line of each test case contains ‘N’ space-separated integers denoting the elements of the doubly linked list.
Output Format :
The only line of output of each test case should contain ‘N’ space-separated integer in the sorted order.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 50
1 <= N <= 500
-10 ^ 9 <= A[i] <= 10 ^ 9
Where ‘A[i]’ is the value of 'ith' node.
Time Limit: 1 sec
Approaches
- The algorithm will remain the same as arrays. We will choose a pivot as the last node in our doubly linked list and define its position in a sorted linked list in linear time. This can be done using partition the list around the pivot.
- We will place all the elements smaller than pivot to the left of the pivot and all the elements greater than pivot will remain at the right side of the pivot. We traverse the list and maintain a pointer that is pointing at the starting of the list. If the current value is smaller than the pivot then we swap the values present at the current node to the starting node pointer and we increment the pointer a step forward.
- Finally, we swap values present at the pointer and pivot node. In this way, the pivot will go to its correct position.
- Now the array is divided into 2 halves around the pivot and we sort them separately by using the same process again for both of them.