Last Updated: 8 Feb, 2021

Sort A “K” Sorted Doubly Linked List

Moderate

Asked in companies

Solve now

Problem statement

You’re given a doubly-linked list with N nodes, where each node deviates at max K position from its position in the sorted list. Your task is to sort this given doubly linked list.

For example :

Let us consider K is 3, an element at position 4 in the sorted doubly linked list, can be at positions 1, 2, 3, 4, 5, 6, 7 in the given linked list because the absolute difference of all these indices with 4 is at most 3.

Note :

All elements are distinct.

A doubly linked list is a type of linked list that is bidirectional, that is, it can be traversed in both directions, forward and backward.

Input Format :

The first line of input contains T, the number of test cases.

The first line of each test case contains an integer K, as specified in the problem statement.

The second line contains the elements of the doubly 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 in a new line the sorted linked list, the elements of the sorted list should be single-space separated, terminated by -1.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10000
1 <= K < N

Time Limit: 1 sec

Solve now

Approaches

01 Approach

We will use Insertion sort to sort the doubly linked list efficiently.

Iterate the given doubly linked list head till the last node n, where n is the size of the doubly linked list.

Compare the current element (key) to its predecessor.
If the key element is smaller than its predecessor, compare elements before. Move the greater elements one position up to make space for the swapped element.

Let’s understand this in a detailed way.

Start by making a Node *current = head and then run a loop till current is not NULL.
Make a Node *back = current -> prev and an integer variable named key = current->data.
Now run a loop till back is not NULL and the key is less than current->data.
Inside this loop update back -> next -> data = back -> data and back= back -> prev.
After exiting this loop check if the back is NULL or not. If it is NULL, then update head -> data = key;
Else update back -> next -> data = key, and after this update current = current -> next.
At last return head, which is our answer.

Solve now

02 Approach

We will start by creating a Min Heap(or a priority queue) of size k+1 with the data of the first k+1 nodes. Also make two pointers named next and prev, where prev points to the previous node and next point to the next node.
We will maintain a priority queue giving priority to the minimum element(min-heap) and we’ll then insert the data of the first k+1 nodes in the queue.
We will run a loop from k+1 till N(Number of nodes in the doubly linked list). We will then start assigning the top element of the queue to the data of the first node of the doubly linked list(we’ll initialize a variable index=0) and then pop this value and also increment the index.
At the same time, we will push the value at which the next pointer is pointing in the loop(it can be from K+1 to N).
After this loop terminates, i.e all the elements from the doubly linked list have been added to the queue. Then, we will just assign the top element of the queue to the linked list and pop that value. We will do this till the queue is empty.
Finally, we will print the K sorted doubly linked list.

Let us understand the working of the above algorithm with the help of an example, where N(Number of nodes in the doubly linked list) = 4, K = 2, and the doubly linked list is:

NULL←5←→6←→2←→3→NULL

We will create a priority queue of size 3(K + 1) and insert the first 3 values {5, 6, 2} in it and also create an integer variable index which is initialized to be 0.
Then we will run a for loop from 3(K + 1) to 4(N) and start assigning the linked list(from the start of the linked list using index variable which was initialized to be 0), to have the value of the top of the queue which will return the value of the smallest value from the queue which will be 2. Hence our first element in the answer linked list is 2, now we will pop this out of the queue and push a new element in the linked list which will be 3.
Now in our case, our loop is terminated as N = 4(Number of nodes in the doubly linked list) has been achieved, so we need not push more elements in the list.
We’ll keep assigning the top element of the queue to our final list, and pop the top element till the queue becomes empty, and finally print the final linked list.
After we pushed 3 in our queue, our 2nd element of our final linked list which is nothing but the top of the queue will be added to the final linked list and our new linked list will look like {2, 3}.
Similarly, we’ll add 5 and 6 to our final linked list and pop them from the queue, and finally now as the queue is empty we’ll just print our final linked list which is {2, 3, 5, 6}.

Solve now