# Sort A “K” Sorted Doubly Linked List

Moderate
0/80
Average time to solve is 15m
Contributed by

## 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
``````
Console