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:

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 elementstruct node *pivot = partition(head , tail);// Recursive calls to quickSortRec procedurequickSortRec(head, pivot);quickSortRec(pivot->next, tail);}void quickSort(struct node **headRef) {node *tail = *headRef;//To find the tailwhile(tail->next != NULL)tail = tail->next;quickSortRec(*headRef, tail);}`
Time Complexity: O(n)

darkmode