# 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 remaining nodes. The solution is simple but we need to make sure that all boundary conditions are handled properly in the code.

C++ implementation –

Output:

1 -> 5 -> 9 -> null

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

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 🙂

Get great deals at Amazon