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:

 

Download   Run Code

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.

 

Download   Run Code

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

 
1 Star2 Stars3 Stars4 Stars5 Stars (3 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

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 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of