# Reverse every alternate group of k nodes in a linked list

Given a linked list, reverse every alternate group of k nodes in it where k is given positive integer.

For example,

Input List : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> null

For k = 2,
Output List: 2 -> 1 -> 3 -> 4 -> 6 -> 5 -> 7 -> 8 -> 10 -> 9 -> null

For k = 3,
Output List: 3 -> 2 -> 1 -> 4 -> 5 -> 6 -> 9 -> 8 -> 7 -> 10 -> null

For k = 1,
Output List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> null

For k >= 10,
Output List: 10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null

### 1. Iterative solution

The idea is to traverse the linked list and consider every group of 2*k nodes at a time. In single iteration of the loop, we reverse the first k nodes and skip the next k nodes. Special care has to be taken while linking reversed groups with the rest of the list.

The algorithm can be implemented as follows:

Output:

Original Linked List : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> null
Resultant Linked List: 2 -> 1 -> 3 -> 4 -> 6 -> 5 -> 7 -> 8 -> 10 -> 9 -> null

### 2. Recursive solution

The recursive solution is similar to the iterative solution where we reverse the first k nodes and skip the next k nodes. But here we recursively call for rest of the list.

Output:

Original Linked List : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> null
Resultant Linked List: 2 -> 1 -> 3 -> 4 -> 6 -> 5 -> 7 -> 8 -> 10 -> 9 -> null

Related Post: Reverse every group of k nodes in given linked list     (3 votes, average: 5.00 out of 5) Loading... 