Sort a "K" Sorted Doubly Linked List Problem Statement

You are given a doubly linked list with 'N' nodes, where each node can deviate at most 'K' positions from its actual position in the sorted list. Your task is to sort this doubly linked list.

Example:

Explanation:

Consider K is 3. An element at position 4 in the sorted doubly linked list can actually be at positions 1, 2, 3, 4, 5, 6, 7 in the provided linked list because the absolute difference between these indices and 4 is at most 3.

Input:

The first line of input contains integer T, the number of test cases.
The first line of each test case contains integer K.
The second line contains the elements of the doubly linked list separated by a single space and terminated by -1. Note that -1 will never be an element of the list.

Output:

For each test case, print the sorted linked list with elements separated by a single space, terminated by -1.

Constraints:

• 1 <= T <= 10
• 1 <= N <= 10000
• 1 <= K < N
• Time Limit: 1 sec

Note:

All elements are distinct.
A doubly linked list is a type of linked list that can be traversed in both directions, forward and backward.
You don’t need to print anything; it is already handled. Implement the given function only.