1.
Introduction
2.
Steps to Solve
2.1.
Implementation in C++
2.2.
Implementation in Java
2.3.
Output
2.4.
Time Complexity:
2.5.
Auxiliary Space Complexity:
3.
3.1.
What kind of memory allocation does a linked list use?
3.2.
Why is it that in a doubly-linked list, deletion is faster?
3.3.
In a binary search tree, what is the difficulty of deletion?
3.4.
What makes a linked list superior to an array?
3.5.
4.
Conclusion
Last Updated: Mar 27, 2024

# Delete N nodes after M nodes of a linked list

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

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 */

}

/* Printing a linked list function */
{
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)
{
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()
{
int M=2, N=3;

cout << "M = " << M<< " N = " << N << "\nLinked list is :\n";

cout<<"\nAfter deletion is :\n";

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;

}

/* Printing a linked list function */
{
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)
{
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[])
{

int M=2, N=3;

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

System.out.printf("\nAfter deletion is :\n");
}
}``````

### Output

``````M = 2, N = 3
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 pre-built class in the collection.

Reason: Here we have used a pre-defined 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

#### What kind of memory allocation does a linked list use?

Linked lists are essentially dynamic data structures, and their operation is based on new and delete (or malloc and free). Normally, the C/C++ standard library manages dynamic memory with the support of the operating system.

#### Why is it that in a doubly-linked list, deletion is faster?

In other words, if you know which cell you want to remove ahead of time, a doubly-linked list allows you to do so in time O(1), but a singly-linked list would take time O(2) (n). In both cases, it's O(n) if you don't know the cell ahead of time. I hope this information was useful.

#### In a binary search tree, what is the difficulty of deletion?

Time complexity is O in general (h). The deletion of element 1 necessitates a traversal of all elements to locate it (in orders 3, 2, 1). As a result, deletion in a binary tree has an O worst-case complexity (n). Time complexity is O in general (h).

#### What makes a linked list superior to an array?

Arrays allow for random access and use less memory per element (since pointers are not used), but they are inefficient for insertion/deletion operations and memory allocation. Linked lists, on the other hand, are dynamic and have faster insertion/deletion times.

#### Is the linked list ordered?

Linked Lists, like stacks and queues, are a type of sequential collection. It doesn't have to be in any particular order. A linked list is a collection of independent nodes that can hold any type of data. Each node in the link has a reference to the next node.

## Conclusion

This article has gone through given a linked list and two integers M and N, to solve the following problem. Linked lists are one of the most basic and widely used data structures. Check out our articles in Library. You may also CheckOut our course on the linked list.

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Ninja, have a great time learning.