Delete N Nodes After M Nodes of a Linked List

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

Difficulty Level: Hard

Here, we are given a linked list and our task is to delete N nodes after M nodes of 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 (N=2,M=2):
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 M nodes of a linked list 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. Also, all the boundary conditions must be handled carefully.

The time complexity of the given solution. will be O(n), where ‘n’ is the number of nodes in the linked list.

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

/* C++ Program to delete N Nodes after M Nodes of a 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);
}
OUTPUT:
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 18

Related Posts:

  1. Delete Complete Linked List.
  2. Delete Nth Node of the Linked List.
  3. Delete without head pointer of the Linked List.
  4. Delete All Occurrences of particular node of the Linked List.
  5. Delete Alternate Nodes of the Linked List.
  6. Remove Duplicate Nodes from an Unsorted Linked List.
  7. Remove Duplicate Nodes from a Sorted Linked List.
  8. Find Union and Intersection of Two Linked List.
  9. Merge Two Sorted Linked List.
  10. Reverse a Linked List.
  11. Reverse a Linked List Using Stack.
  12. Printing Linked List in Reverse Order without actually reversing the Linked List.
  13. Swap Adjacent Elements of the Linked List.
  14. Count All Occurrences of a Particular Node in a Linked List.
  15. Bubble Sort on Linked List.
  16. Detect a Loop in a Linked List.
  17. Find the Length of the Loop present in the Linked List.
  18. Detect and Remove Loop from a Linked List.
  19. Segregate Even and Odd Nodes of the Linked List.
  20. Program to find equilibrium index of an Array.

You may also like...