Last Updated: 23 Nov, 2020
Quick Sort on Linked List
Moderate
Asked in companies
You are given a Singly Linked List of integers. Sort the Linked List using Quick Sort Algorithm.
Quick Sort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot such that the elements before the pivot are less than the pivot and all the elements greater than or equal to the pivot come after the pivot.
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 singly 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 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 <= L <= 10 ^ 2
- 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 and 'DATA' is the value of any node in the given linked list.
Time limit: 1 sec.
Approaches
We can recursively sort the linked list by using the Quick Sort algorithm.
Note: head points to the first element and tail points to the last element of the linked list.
For finding the tail, we will traverse the list until we have found a node whose ‘next’ value is NULL.
Recursive State: Node *quickSortHelper( Node *head, Node *tail ), it will return the new head after sorting the list.
Base Case: When head and tail point to the same node or head is NULL, we will return the head.
- Pick an element as pivot, we will pick the last element as pivot.
- Make a function partition which will partition the list around the picked pivot. In this function, we traverse through the current list and if a node has a value greater than the pivot, we move it after tail. If the node has a smaller value, we keep it at its current position.
- In the partition function, we will pass the reference of new head and new tail, which will be initially NULL and after the partition of the list, we will get the updated new head and new tail.
- The partition function will return a pointer which points to the pivot.
- We have found the correct position for the pivot element, now will call the recursive function for the left part and the right part of the pivot element.
- Find the tail of the left part and update it’s ‘next’ value such that it points to the pivot node.
- Update the ‘next’ value of the pivot node such that it points to the head of the right part.