Delete every N nodes in a linked list after skipping M nodes

Given a linked list and two positive integers M and N, delete every N nodes in it after skipping M nodes.

 

For example, consider below list,


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

If M = 1, N = 3
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> null
1 -> 5 -> 9 -> null
 

If M = 2, N = 2
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> null
1 -> 2 -> 5 -> 6 -> 9 -> 10 -> null

 


 

The idea is very simple. We traverse the given list and skip first m nodes and delete next n nodes in it and recurse for remaning nodes. The solution is simple but we need to make sure that all boundary conditions are handled properly in the code.

 
C++ implementation –
 

Download   Run Code

Output:

1 -> 5 -> 9 -> null

 

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

 
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 🙂