New update is available. Click here to update.

Last Updated: 2 Dec, 2020

Moderate

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

```
If the number of nodes in the list or in the last group is less than K, just reverse the remaining nodes.
```

```
Linked list: 8 9 10 11 12
K: 3
Output: 10 9 8 12 11
We reverse the first K (3) nodes. Now, since the number of nodes remaining in the list (2) is less than K, we just reverse the remaining nodes (11 and 12).
```

```
The first line of input contains an integer T, the number of test cases.
The first line of every test case contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.
The second line of every test case contains the positive integer βKβ.
```

```
For every test case, print the modified linked list. The elements of the modified list should be single-space separated, terminated by -1.
```

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 10
1 <= N <= 5 * 10^4
1 <= K <= 10^5
-10^3 <= data <= 10^3 and data != -1
Time Limit: 1 sec
```

Approaches

The idea is very simple. We will process βKβ nodes at a time. Firstly, we will reverse the first βKβ nodes of the doubly linked list and then we will do this recursively for the remaining linked list.

**Algorithm:**

- If the node does not exist, simply return βNULLβ.
- βHEADβ is pointing to the first node of the linked list.
- If there are less than βKβ nodes, just reverse them and return the reversed linked list. Else reverse the first βKβ nodes of the linked list.
- After reversing the βKβ nodes, the head points to the Kth node and the Kth node in the original linked list will become the new head.
- To connect the reversed part with the remaining part of the linked list, update the next of the head to (K + 1)th node and the previous of the (K + 1)th node to the head node.
- Now, recursively modify the rest of the linked list and link the two sub-linked lists.
- Return the new head of the linked list.

The idea is the same as used in the previous approach. This time, we will do it iteratively.

- Head is pointing to the first node of the linked list.
- Initialise a pointer to a Node βNEW_HEADβ that will point to the head of the final modified linked list.
- Repeat the steps below until all the nodes are processed in the same way.

- Reverse the first βKβ nodes of the linked list.
- After reversing the βKβ nodes, the head points to the Kth node.
- If the newHead is βNULLβ,
- If the Kth node in the original linked list exists, it will be the βNEW_HEADβ.
- Else, the last node in the original linked list will be the βNEW_HEADβ.

- To connect the reversed part with the remaining part of the linked list, update the next of the head to (K + 1)th node and the previous of the (K + 1)th node to the head node.
- Return the new head of the linked list.

Note that we just have to set the new head once.

Similar problems

Deletion In Doubly Linked List

Easy

Posted: 22 Apr, 2022

Deletion In Doubly Linked List

Easy

Posted: 22 Apr, 2022

Insertion In Doubly Linked List

Easy

Posted: 24 Apr, 2022

LRU Cache

Moderate

Posted: 10 Sep, 2022

Delete Nodes On Regular Intervals

Ninja

Posted: 19 Dec, 2022

Add One To Linked List

Hard

Posted: 19 Dec, 2022