Reverse K alternate nodes in linked list

Reverse K alternate nodes in linked list

Given a linked list, reverse K alternate nodes of it. For example,

Example 1:
Original list : 1->2->3->4->5->6 K = 2;
Output list : 2->1->3->4->6->5 

Example 2:
Original list : 1->2->3->4->5->6->7->NULL K = 3;
Output list : 3->2->1->4->5->6->7

In above example 1, K =2, so first two nodes are reversed, next two nodes remain as such and then next two nodes are again reversed. Similarly, in next example, K =3, hence first three nodes are reversed, next three are not and then remaining one node is reversed. Hope example clarifies the problem!

Now, let’s look for solution. There are two ways to reverse K alternate nodes of linked list.

Iterative/Recursive way to reverse k alternate nodes

This is approach is very similar to what we learned when we solve reversing linked in group of given size. Only thing which is different here is we need to skip next K nodes once we have reversed K nodes.

1. Reverse first K nodes. Keep track of previous node, to be returned.
2. Connect head of these K nodes to node next to last node in these K nodes. (head->next = next)
3. Skip next K nodes.
4. Now connect next node of last node to value returned from recursion.
5. Return previous node, i.e last node of these K nodes.
At the end of recursion, last previous returned will become head of linked list.

Code to iterative reverse K nodes of linked is very simple.

Pure recursive way to reverse K alternate nodes

In this method, we will go with a flag, based on flag we will decide if current batch of K nodes will be reversed or not.

1. If flag is true, reverse K nodes
2. If flag is not true, skip K nodes.
3. Recurse to process next n-K nodes of linked list

Output

Original list: 8->7->6->5->4->3->Null
Reverse list : 7->8->6->5->3->4->Null
Original list: 10->8->7->6->5->4->3->Null
Reverse list : 8->10->7->6->4->5->3->Null

Complexity of both algorithms to reverse K alternate of linked list is O(n).
Do share if there are any comments or suggestions for improvements. Sharing is caring!