# 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:

- If linked list is empty, then return.
- Start traversing the linked list.
- While traversing, traverse every M nodes and after traversing M nodes, delete every N nodes.
- 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 */ void insert_end(Node **head, int ele) { /* 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 { *head = new_node; 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; temp = (*head); while(temp->next != NULL) temp=temp->next; temp->next = new_node; } /* Function to Delete Every N Nodes after M Nodes */ void delete_N_after_M_nodes(Node *head,int N,int M) { /* If Linked List is empty, simply return */ if(head == NULL) return; /* Traverse the complete linked list. While traversing, traverse every M nodes and after traversing M nodes, delete every N nodes. */ Node *temp = head; 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 */ void print(Node *head) { Node *temp = head; while(temp!=NULL) { cout<<temp->data<<" "; temp=temp->next; } cout<<endl; } int main() { Node *head = NULL; /* Inserting Some Nodes in the Linked List */ insert_end(&head,12); insert_end(&head,13); insert_end(&head,14); insert_end(&head,15); insert_end(&head,16); insert_end(&head,17); insert_end(&head,18); cout<<"Linked List before deleting every 1 node after 2 Nodes is:\n"; print(head); int N = 1; int M = 2; delete_N_after_M_nodes(head,N,M); cout<<"\nLinked List after deleting every 1 node after 2 Nodes is:\n"; print(head); }

Linked List before deleting every 1 node after 2 Nodes is: 12 13 14 15 16 17 18 Linked List after deleting every 1 node after 2 Nodes is: 12 13 15 16 18OUTPUT:

**Related Posts:**

**Delete Complete Linked List.****Delete Nth Node of the Linked List.****Delete without head pointer of the Linked List.****Delete All Occurrences of particular node of the Linked List.****Delete Alternate Nodes of the Linked List.****Remove Duplicate Nodes from an Unsorted Linked List.****Remove Duplicate Nodes from a Sorted Linked List.****Find Union and Intersection of Two Linked List.****Merge Two Sorted Linked List.****Reverse a Linked List.****Reverse a Linked List Using Stack.****Printing Linked List in Reverse Order without actually reversing the Linked List.****Swap Adjacent Elements of the Linked List.****Count All Occurrences of a Particular Node in a Linked List.****Bubble Sort on Linked List.****Detect a Loop in a Linked List.****Find the Length of the Loop present in the Linked List.****Detect and Remove Loop from a Linked List.****Segregate Even and Odd Nodes of the Linked List.****Program to find equilibrium index of an Array.**