Delete N nodes after M  

In the given linked list delete N nodes after M nodes, do this till the end of the linked list.  



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.

Please click Like if you loved this article?

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;    
    if(*head == NULL)
            *head=curr; //if this is first node make this as head of list
            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
//display linked list
void display(struct LLNode**node)
    struct LLNode *temp= *node;
            cout<<temp->data<<" ->";
            temp=temp->next; //move to next node
        //O(number of nodes)

void DeleteNAfterM(struct LLNode  *head, int M, int N)
    struct LLNode *curr = head, *rem;
    int count;
    //Move M nodes and delete N nodes
        for (count = 1; count<M && curr!= NULL; count++)
            curr = curr->next;
        if (curr == NULL)
        rem = curr->next;
        for(count = 1; count<=N && rem!= NULL; count++)
            struct LLNode *temp = rem;
            rem = rem->next;
        //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;
    insertAtBeginning(&head, 8);
    insertAtBeginning(&head, 7);
    insertAtBeginning(&head, 6);
    insertAtBeginning(&head, 5);
    insertAtBeginning(&head, 4);
    insertAtBeginning(&head, 3);
    insertAtBeginning(&head, 2);
    insertAtBeginning(&head, 1);
    cout<<"Given M = "<<M<<", "<<"N = "<<N<<endl;
    cout<<"Input linked list: ";

    DeleteNAfterM(head, M, N);
    cout<<"Output linked list: ";
    return 0;

See also
Merge K Sorted Linked Lists


Please click Like if you loved this article?