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;
}

 

Translate ยป