Quick Sort on Linked List

Sort the given Linked List using quicksort. which takes O(n^2) time in worst case and O(nLogn) in average and best cases, otherwise you may get TLE.

Input:

In this problem, method takes 1 argument: address of the head of the linked list. The function should not read any input from stdin/console.

The struct Node has a data part which stores the data and a next pointer which points to the next element of the linked list.

There are multiple test cases. For each test case, this method will be called individually.

Output:

Set *headRef to head of resultant linked list.

User Task:

The task is to complete the function quickSort() which should set the *headRef to head of the resultant linked list.

Constraints:

1<=T<=100

1<=N<=200

Note: If you use "Test" or "Expected Output Button" use below example format

Example:

Input:

2

3

1 6 2

4

1 9 3 8

Output:

1 2 6

1 3 8 9

Explanation:

Testcase 1: After sorting the nodes, we have 1, 2 and 6.

Testcase 2: After sorting the nodes, we have 1, 3, 8 and 9.

c++ implementation:

struct node * partition(struct node *head, struct node *tail){
node * prev=head, *cur=head->next;
node *pivot = head;
while(cur != tail->next)
{
if(cur->data < pivot->data)
{
prev = prev->next;
swap(prev->data,cur->data);
}
cur = cur->next;
}
swap(pivot->data,prev->data);
return prev;
}

void quickSortRec(struct node * head, struct node *tail){
if(head == tail || tail == NULL || head == NULL )
return;
// To find the pivot element
struct node *pivot = partition(head , tail);

// Recursive calls to quickSortRec procedure
quickSortRec(head, pivot);
quickSortRec(pivot->next, tail);
}

void quickSort(struct node **headRef) {
node *tail = *headRef;
//To find the tail
while(tail->next != NULL)
tail = tail->next;
quickSortRec(*headRef, tail);
}

Time Complexity: O(n)