Delete N nodes after M nodes in linked list

Delete N nodes after M nodes in linked list

Given a singly linked list, delete N nodes after M nodes. By delete n nodes after m nodes, we mean that start from head of list, skip M nodes, then delete next N nodes, again skip M nodes, then delete N nodes and so on till end of list.  Example:

List : 1->2->3->4->5->6->7->8->Null N =2, M =3
Output : 1->2->3->6->7->8-Null

In above example,  three nodes: 1,2 and 3 are skipped, then 2 nodes:4,5 are deleted and then again next three nodes 6,7,and 8 are skipped and then linked list is finished.

This problem is very simple and needs only traversal of linked list. All we need to do is to keep track of last node of skipped M nodes and next node of N deleted node. Link this two list and we are done. Start the same process again from next node of N delete node. Algorithm will be:

1. Start from head of list
2. Traverse M nodes, keep track of last node (current)
3. Start from next node after step, and delete N nodes.
4. Get the next node of step 3. (next)
5. Connect node in step 2 and step 4 current->next = next

Delete N nodes after M nodes in linked list : iterative implementation

Complexity of iterative method to delete n nodes after m nodes in a linked list is O(n). There is no additional space required.

Another method is to recursively delete and skip nodes. In this implementation, we pass a flag to the function, which indicates if nodes are to be deleted or skipped. We already used this approach previously, to solved problem reverse K alternate nodes of linked list.

Recursive algorithm to delete n nodes after m nodes

1. Start with head node and skipNodes flag as true
2. While there are nodes in list
   2.a If skipNodes flag is true, simply scan the m nodes in list
   2.b Reverse the flag.
   2.c If skipNodes flag is false, delete n nodes
   2.d reverse flag and link last node in 2.a and 2.c

Output

Input : 4->2->1->9->8->7->6->Null N=3, M=3
Output: 4->2->1->6->Null

Input : 4->2->1->9->8->7->6->Null N=3, M=4
Output: 4->2->1->9->Null

Complexity of recursive implementation is O(n). However, there is implicit space requirement due to recursion.

Please share your thoughts, or if there is something is wrong, please leave a comment. Sharing is caring.