# Reverse every group of k nodes in given linked list

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

For example,

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

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

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

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

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

The idea is to consider every group of k nodes and recursively reverse them one by one. Special care has to be taken while linking reversed groups with each other.

C++ implementation –

Output:

3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 8 -> 7 -> null

Above solution returns head node pointer from the function. Alternatively, we can pass pointer (reference) to the head node to reverseInGroups() function and avoid updating head pointer insider the main() function.

C++ implementation –

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

Exercise:
Modify the solution to reverse every alternate group of k nodes.