# Delete N nodes after M

0
211

## Algorithm

a. Traverse through the list.

b. Skip M nodes, if we reach the end of list then return.

c. Else, delete next N nodes and link the list with remaining nodes.

d. Continue next iteration by moving the pointer.

## C++ Program

``````#include <bits/stdc++.h>

using namespace std;

struct LLNode
{
int data;
struct LLNode* next;
};

/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
struct LLNode* curr = new LLNode;
curr->data = dataToBeInserted;
curr->next = NULL;
*head=curr; //if this is first node make this as head of list

else
{
curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
}

//O(1) constant time
}

void display(struct LLNode**node)
{
struct LLNode *temp= *node;
while(temp!=NULL)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;

temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}

void DeleteNAfterM(struct LLNode  *head, int M, int N)
{
struct LLNode *curr = head, *rem;
int count;
//Move M nodes and delete N nodes
while(curr)
{
for (count = 1; count<M && curr!= NULL; count++)
{
curr = curr->next;
}
if (curr == NULL)
{
return;
}
rem = curr->next;
for(count = 1; count<=N && rem!= NULL; count++)
{
struct LLNode *temp = rem;
rem = rem->next;
free(temp);
}
//link to remaining nodes
//continue iteration for the remaining nodes
curr->next = rem;
curr = rem;
}
}

//Main function
int main()
{
struct LLNode* head = NULL;
int M=2, N=2;