Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Sort A “K” Sorted Doubly Linked List

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

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 )
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
Full screen
Console