Introduction
This article will teach to solve a question where given a linked list and two integers M and N, solve the following problem. Continue traversing the linked list in this manner: keep M nodes, then delete the following N nodes, and so on until you reach the end.
Recommended Topic, Floyds Algorithm
Steps to Solve

For the linked list node, create a struct Node.

Use the dummy data to populate the linked list.

Create a method that deletes N nodes after M.

Use the head pointer to create a pointer.

Iterate until you've reached the end of the linked list.

Continue moving the pointer to the next node until M nodes have been reached.

N nodes should be removed.
 Navigate to the next node with the cursor.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
// linked list node
class Node
{
public:
int val;
Node *next;
};
void push(Node ** headnode_refer, int new_val)
{
/* allocating node */
Node* new_node = new Node();
new_node>val = new_val;
/*the old list is linked to the new node */
new_node>next = (*head_refer);
/* Point to the new node with your head. */
(*head_refer) = new_node;
}
/* Printing a linked list function */
void printList(Node *headnode)
{
Node *tp = headnode;
while (tp != NULL)
{
cout<<tp>val<<" ";
tp = tp>next;
}
cout<<endl;
}
// N nodes in the connected list should be removed..
void delMN(Node *headnode, int M, int N)
{
Node *curr = headnode, *t;
int ct;
// traverses whole list
while (curr)
{
for (ct = 1; ct < M &&
curr!= NULL; ct++)
curr = curr>next;
//Return if we've reached the end of the list.
if (curr == NULL)
return;
//Begin with the next node and work your way through the list, deleting N nodes at a time.
t = curr>next;
for (ct = 1; ct<=N && t!= NULL; ct++)
{
Node *tp = t;
t = t>next;
free(tp);
}
// Connect the nodes in the previous list to the ones that remain.
curr>next = t;
// Set the current pointer to the next iteration's value.
curr = t;
}
}
int main()
{
/* Creating linked list */
Node* headnode = NULL;
int M=2, N=3;
push(&headnode, 10);
push(&headnode, 9);
push(&headnode, 8);
push(&headnode, 7);
push(&headnode, 6);
push(&headnode, 5);
push(&headnode, 4);
push(&headnode, 3);
push(&headnode, 2);
push(&headnode, 1);
cout << "M = " << M<< " N = " << N << "\nLinked list is :\n";
printList(headnode);
delMN(headnode, M, N);
cout<<"\nAfter deletion is :\n";
printList(headnode);
return 0;
}
Implementation in Java
import java.util.*;
class DeleteMN
{
static class Node
{
int val;
Node next;
};
static Node push( Node head_refer, int new_val)
{
/* allocate node */
Node new_node = new Node();
/* put in the val */
new_node.val = new_val;
new_node.next = (head_refer);
(head_refer) = new_node;
return head_refer;
}
/* Printing a linked list function */
static void printList( Node headnode)
{
Node tp = headnode;
while (tp != null)
{
System.out.printf("%d ", tp.val);
tp = tp.next;
}
System.out.printf("\n");
}
//The function skips M nodes in the linked list and then deletes N nodes.
static void delMN( Node headnode, int M, int N)
{
Node curr = headnode, t;
int ct;
// The main loop that iterates across the entire list
while (curr!=null)
{
for (ct = 1; ct < M && curr != null; ct++)
curr = curr.next;
// Return if we've reached the end of the list.
if (curr == null)
return;
//Begin with the next node and delete N nodes.
t = curr.next;
for (ct = 1; ct <= N && t != null; ct++)
{
Node tp = t;
t = t.next;
}
// Connect the nodes in the previous list to the ones that remain.
curr.next = t;
// Set the current pointer to the next iteration's value.
curr = t;
}
}
public static void main(String args[])
{
Node headnode = null;
int M=2, N=3;
headnode=push(headnode,10);headnode=push(headnode, 9);
headnode=push(headnode, 8);headnode=push(headnode, 7);
headnode=push(headnode, 6);headnode=push(headnode, 5);
headnode=push(headnode, 4);headnode=push(headnode, 3);
headnode=push(headnode, 2);headnode=push(headnode, 1);
System.out.printf("M = %d, N = %d \n" +
"Linked list is :\n", M, N);
printList(headnode);
delMN(headnode, M, N);
System.out.printf("\nAfter deletion is :\n");
printList(headnode);
}
}
Output
M = 2, N = 3
Linked list is :
1 2 3 4 5 6 7 8 9 10
After deletion is :
1 2 6 7
Time Complexity:
O(N) Where N stands for the length of the Linked list.
Reason: O(N) time, this is because we have to iterate from start to end. The program deletes N nodes after skipping M nodes in the linked list. Begin with the next node on the list and work your way down, eliminating N nodes at a time.
Auxiliary Space Complexity:
O(1) as stored in the single data structure which is defined in the prebuilt class in the collection.
Reason: Here we have used a predefined data structure from the collection. As a function of input attributes, the amount of memory space required to solve an instance of the computational problem is set to one.
Recommended Topic, Floyds Algorithm