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

Problem of the day

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.

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

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

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

```
1
4
6 5 3 2 8 10 9 -1
```

```
2 3 5 6 8 9 10 -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.
```

```
1
4
10 9 8 7 4 70 60 50 -1
```

```
4 7 8 9 10 50 60 70 -1
```