# 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

Output:

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

## Java

Output:

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

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

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

Exercise: Modify the solution to reverse every alternate group of k nodes.     (1 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest

Is recursion is not going to take any space ? if it is going to take space how can space complexity be O(1) Guest
arandomguy

Aren’t prev and result in reverseK same? So why use both? Use only one, right?