Home » Interview Questions » LinkedList Interview Questions » Delete N nodes after M

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.

Example

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;    
    if(*head == 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
            *head=curr;
        }
        
        //O(1) constant time
}
 
//display linked list
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;
    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: ";
    display(&head);

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

READ  Swap nodes in the linked list

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions