Problem title
Difficulty
Avg time to solve

Generate all parenthesis
Moderate
30 mins
Convert BST to Min Heap
Moderate
25 mins
Min Steps to one
Easy
15 mins
Construct BST from Level Order
Easy
15 mins
Minimum number of swaps required to sort an array
Easy
10 mins
Median in a stream
Hard
50 mins
Sort an array in wave form
Easy
10 mins
Fractional Knapsack
Easy
15 mins
Move Zeros To Left
Easy
10 mins
Longest Repeating Subsequence
Moderate
15 mins 15

# Sort A “K” Sorted Doubly Linked List

Difficulty: MEDIUM
Avg. time to solve
15 min
Success Rate
85%

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