QuickSort On Doubly Linked List

Hard

0/120

Average time to solve is 20m

Contributed by

4 upvotes

Asked in company

Problem statement

You are given the head of Doubly Linked List containing ‘N’ nodes. Each node will have an integer value stored in it. You need to return the head of the Doubly linked list after sorting it using the QuickSort algorithm.

For example :

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of the input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single positive integer ‘N’ denoting the number of the element nodes present in the doubly linked list.

The second line of each test case contains ‘N’ space-separated integers denoting the elements of the doubly linked list.

Output Format :

The only line of output of each test case should contain ‘N’ space-separated integer in the sorted order.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 50
1 <= N <= 500
-10 ^ 9 <= A[i] <= 10 ^ 9

Where ‘A[i]’ is the value of 'ith' node.

Time Limit: 1 sec

Sample Input 1 :

Sample Output 1 :

-3 2 4 4
2 3 3 4 4

Explanation for sample input 1:

Test case 1 :
After sorting the list [4,2,-3,4] will look like [-3,2,4,4].

Test case 2 :
After sorting the list [4,2,-3,4] will look like [-3,2,4,4].

Sample Input 2 :

2
5 
45 -2 42 5 -11 
6 
-2 12 -1 1 20 1

Sample Output 2 :

-11 -2 5 42 45
-2 -1 1 1 12 20

Hint 1

Instead of swapping nodes, you can swap values present in the node.

Approaches (1)

Approach 1

QuickSort

The algorithm will remain the same as arrays. We will choose a pivot as the last node in our doubly linked list and define its position in a sorted linked list in linear time. This can be done using partition the list around the pivot.
We will place all the elements smaller than pivot to the left of the pivot and all the elements greater than pivot will remain at the right side of the pivot. We traverse the list and maintain a pointer that is pointing at the starting of the list. If the current value is smaller than the pivot then we swap the values present at the current node to the starting node pointer and we increment the pointer a step forward.
Finally, we swap values present at the pointer and pivot node. In this way, the pivot will go to its correct position.
Now the array is divided into 2 halves around the pivot and we sort them separately by using the same process again for both of them.

Time Complexity

O(N^2), where ‘N’ is the number of nodes present in the array.

In each recursive call, we do O(N) operations. And in the worst case, we may have ‘N’ recursive calls in the stack which will make the time complexity to be O(N^2).

Space Complexity

O(N), where ‘N’ is the number of nodes present in the array.

In the worst case, the recursive function stack can contain ‘N’ entries.

(100% EXP penalty)

QuickSort On Doubly Linked List

Console