Quick Sort on Linked List

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
23 upvotes
Asked in companies
SprinklrDatametica Solutions Private Limited

Problem statement

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.

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 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.
Sample Input 1:
3
1 -2 3 -1
9 9 -1
4 -1
Sample Output 1:
-2 1 3 -1
9 9 -1
4 -1
Explanation for Sample Input 1:
For every test case, the sorted list is printed, terminated by -1.
Sample Input 2:
2
1 1 1 -1
3 -3 -1
Sample Output 2:
1 1 1 -1
-3 3 -1
Hint

Think of the same way, you would sort an array using Quick Sort, but for the linked list, we will change pointers rather than swapping data.

Approaches (1)
Divide and Conquer

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.
Time Complexity

O(L ^ 2), where ‘L’ is the number of nodes in the linked list.
 

In the worst case, it takes O(L) time to partition the list and O(L) time to find the tail of the list.

In average and best cases, recursion will take O(log(L)) time but in the worst case(when the list is already sorted in any order) it takes O(L) time. 

Thus the final complexity will O(L * log(L)) in average and best case, and O(L ^ 2) in the worst case.

Space Complexity

O(L), where ‘L’ is the number of nodes in the linked list.
 

There can be at most ‘L’ recursive states, so O(L) additional space is required.

Code Solution
(100% EXP penalty)
Quick Sort on Linked List
Full screen
Console