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;


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