Sort A “K” Sorted Doubly Linked List

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
32 upvotes
Asked in companies
D.E.ShawJosh Technology GroupNagarro Software

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
1
4 
6 5 3 2 8 10 9 -1
Sample Output 1 :
2 3 5 6 8 9 10 -1
Explanation For Sample Input 1 :
We could move 6 from position 1 to as far as position 5(as K=4) and we moved it to position 4 and it can be seen that after that all elements to the left(i.e position 1 to 3) are less than 6, hence 10 is at its best position now. Similarly, we do this for all the elements, to reach our answer.
Sample Input 2 :
1
4
10 9 8 7 4 70 60 50 -1
Sample Output 2 :
4 7 8 9 10 50 60 70 -1
Approaches (2)
Insertion Sort 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.
Time Complexity

O(N * K), where N is the number of elements in the doubly linked list and K is the maximum deviation of an element from its target position. 

 

In the worst case, to move every element to its correct place, at most K elements need to be moved.

Space Complexity

O(1)

 

As we are using constant extra memory.

Code Solution
(100% EXP penalty)
Sort A “K” Sorted Doubly Linked List
Full screen
Console