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

Download   Run Complete Code

Output:

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

Java

Download   Run Code

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

Download   Run Code

 
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.

 
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

avatar
  Subscribe  
newest oldest most voted
Notify of
shekar
Guest

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

arandomguy
Guest

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