# Delete Every N Nodes After M Nodes of the Linked List

Delete Every N Nodes After M Nodes of the Linked List” is one of the foremost  problem asked in many technical and algorithmic interviews of various product based companies.

Here, we are given a linked list and our task is to delete every ‘N’ nodes after every ‘M’ nodes in a linked list. This pattern will continue till end of the linked list.

```For example, we need to delete 2 nodes after leaving every 2 nodes in a following linked list:
LINKED LIST:       12 -> 13 -> 14 -> 15 -> 16 -> 17
After deleting,
LINKED LIST:       12 -> 13 -> 16 -> 17
Other Example:
N = 1, M = 2
LINKED LIST:      12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 18
After deleting,
LINKED LIST:       12 -> 13 -> 15 -> 16 -> 18```

The steps required to delete N nodes after leaving every M nodes are as follows:

1. If linked list is empty, then return.
2. Start traversing the linked list.
3. While traversing, traverse every M nodes and after traversing M nodes, delete every N nodes.
4. This will continue till the end of the linked list.

The major task here is to handle the links or pointers while traversing and deleting nodes of a linked list.

C++ Program to delete N nodes after M nodes in a linked list is as follows:

```/* C++ Program to delete N Nodes after M Nodes of the Linked List */
#include<bits/stdc++.h>
using namespace std;

/* Structure of the node of the linked list */
typedef struct node
{
int data;
struct node *next;
}Node;

/* Function to Insert node at the end of the linked list */
{
/* Creating a new node */
Node *new_node;
new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = ele;
new_node->next = NULL;

/* check whether the linked list is empty or not */

/* If Linked List is empty, then new node will become head of the linked list */
if(*head == NULL)     // if empty
{
return;
}

/* If Linked List is not empty, then traverse the complete linked list and point the pointer
of last node of the linked list to the new node */
Node *temp = NULL;
while(temp->next != NULL)
temp=temp->next;
temp->next = new_node;
}

/* Function to Delete Every N Nodes after M Nodes */
{
/* If Linked List is empty, simply return  */
return;
/*
While traversing, traverse every M nodes and
after traversing M nodes, delete every N nodes.
*/
Node *prev = NULL;
while(temp!=NULL)
{
for(int i = 1 ; i <= M && temp != NULL ; i++)
{
prev = temp;
temp = temp -> next;
}
if(temp == NULL)
return;
for(int i = 1 ; i <= N && temp != NULL ; i++)
{
Node *p = temp;
temp = temp -> next;
free(p);
}
if(temp == NULL)
prev -> next = NULL;
else
prev -> next = temp;
}
}

/* Function to Print the Linked List  */
{
while(temp!=NULL)
{
cout<<temp->data<<" ";
temp=temp->next;
}
cout<<endl;
}
int main()
{
/* Inserting Some Nodes in the Linked List */
cout<<"Linked List before deleting every 1 node after 2 Nodes is:\n";
int N = 1;
int M = 2;
cout<<"\nLinked List after deleting every 1 node after 2 Nodes is:\n";
```OUTPUT: