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)  


darkmode