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 –
 

Download   Run Complete Code

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 –
 

Download   Run Code

 

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.

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz