# Delete N nodes after M nodes of a Linked List ### Introduction

The linked list is one of the most important data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

### Problem Statement

In this question, we are given a singly linked list, a value M and a value N. We have to delete N nodes after M nodes of the given list. This means that we will keep M nodes, and delete N nodes, and will continue this till we reach the end of the linked list.

### Problem Statement Understanding

Let the given list be 1 -> 2 -> 3 -> 4 -> 56 -> 45 -> 7 -> 8 and the value of M=2 and N=2. This means that after every 2 node, we will delete 2 nodes.

So, in the first step, our linked list will be 1 -> 2 -> 56 -> 45 -> 7 -> 8 . As we can see, we have removed the 3rd and 4th nodes from the list. Now, in the second step, our linked list will be 1 -> 2 -> 56 -> 45. Now, we have reached the tail of the list.

So, the final linked list is 1 - > 2 - > 56 - > 45.

Input: M=2, N=2 Output: Explanation: As the value of M is 2 and the value of N is 2, we will retain 2 nodes and delete 2 nodes till we reach the end of the list.

This is an interesting question. It is not a complex one, but we have to look out for all the edge cases. Let us have a glance at the approach.

### Approach

We are going to make use of list traversal here. First, we will skip M nodes. Now, if we reach the end of the list, then we will terminate the method, else, we will store the address of the Mth node in the current and temp will point to the (M+1)th node which is next of current. Now, we will traverse the next N nodes, and increment temp. In the end, we will make the Mth node point to the temp, and temp will become our new current.

### Algorithm

• Create a node current, and make it point to the head.
• Traverse through the list till the end is reached.
• Skip M nodes. We can do this with the help of a for loop. In every iteration, do current = current -> next.
• Now, if the current becomes NULL, it means that we have reached the end of the list. We will terminate the method.
• Else, store the next of current in temp. Write a for loop that runs N times, and increment temp by 1 in each iteration.
• After the loop, make the current point to temp.
• The temp will become our new current.

### Dry Run ### Code Implementation

```#include <stdio.h>
#include <stdlib.h>

struct Node
{
int data;
struct Node *next;
};

/* Function to insert a node at the beginning */
void push(struct Node ** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

new_node->data  = new_data;

}

{
while (temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
void skipMdeleteN(struct Node  *head, int M, int N)
{
struct Node *curr = head, *t;
int count;

while (curr)
{
// Skip M nodes
for (count = 1; count<m &&="" curr!="NULL;" count++)="" curr="curr-">next;
if (curr == NULL)
return;

t = curr->next;
for (count = 1; count<=N && t!= NULL; count++)
{
struct Node *temp = t;
t = t->next;
free(temp);
}
curr->next = t; // Link the previous list with remaining nodes

curr = t;
}
}

// Driver program to test above functions
int main()
{
int M=2, N=3;

printf("M = %d, N = %d \nGiven Linked list is :\n", M, N);

printf("\nLinked list after deletion is :\n");

return 0;
}
```
```#include <bits stdc++.h="">
using namespace std;

class Node
{
public:
int data;
Node *next;
};

void push(Node ** head_ref, int new_data)
{
Node* new_node = new Node();

new_node->data = new_data;

}

{
while (temp != NULL)
{
cout<<temp->data<<" ";
temp = temp->next;
}
cout<<endl; }="" void="" skipmdeleten(node="" *head,="" int="" m,="" n)="" {="" node="" *curr="head," *t;="" count;="" while="" (curr)="" for="" (count="1;" count="" <="" m="" &&="" curr!="NULL;" count++)="" curr="curr-">next;

if (curr == NULL)
return;

t = curr->next;
for (count = 1; count<=N && t!= NULL; count++)
{
Node *temp = t;
t = t->next;
free(temp);
}

curr->next = t;

curr = t;
}
}

int main()
{

int M=2, N=2;
cout << "M = " << M<< " N = " << N << "\nGiven Linked list is :\n";

cout<<"\nLinked list after deletion is :\n";

return 0;
}
```
```import java.util.*;

public class PrepBytes
{

static class Node
{
int data;
Node next;
};

static Node push( Node head_ref, int new_data)
{
Node new_node = new Node();

new_node.data = new_data;

}

{
while (temp != null)
{
System.out.printf("%d ", temp.data);
temp = temp.next;
}
System.out.printf("\n");
}

static void skipMdeleteN( Node head, int M, int N)
{
int count;

while (curr!=null)
{
// Skip M nodes
for (count = 1; count < M && curr != null; count++)
curr = curr.next;

if (curr == null)
return;

t = curr.next;
for (count = 1; count <= N && t != null; count++)
{
Node temp = t;
t = t.next;
}

curr.next = t;

curr = t;
}
}

public static void main(String args[])
{

int M=2, N=2;
System.out.printf("M = %d, N = %d \nGiven" +
"Linked list is :\n", M, N);

System.out.printf("\nLinked list after deletion is :\n");
}
}
```
```class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def push(self, new_data):
new_node = Node(new_data)

def printList(self):
while(temp):
print (temp.data,end=" ")
temp = temp.next

def skipMdeleteN(self, M, N):

while(curr):
# Skip M nodes
for count in range(1, M):
if curr is None:
return
curr = curr.next

if curr is None :
return

t = curr.next
for count in range(1, N+1):
if t is None:
break
t = t.next

curr.next = t
curr = t

M = 2
N = 2
llist.push(8)
llist.push(7)
llist.push(45)
llist.push(56)
llist.push(4)
llist.push(3)
llist.push(2)
llist.push(1)

print ("M = %d, N = %d\nGiven Linked List is:" %(M, N))
llist.printList()
print()

llist.skipMdeleteN(M, N)

print ("\nLinked list after deletion is")
llist.printList()

```