Delete N nodes after M nodes of a Linked List

In this tutorial, we are going to learn how to Delete N nodes after M nodes of a Linked List. Let’s see the problem statement for a better understanding.

Problem Statement of Delete N nodes after M nodes of a Linked List

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, delete N nodes, and will continue this till we reach the end of the linked list.

Problem Statement Understanding of Delete N nodes after M nodes of a Linked List

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 nodes, 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 on how to Delete N nodes after M nodes of a Linked List

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 of how to Delete N nodes after M nodes of a Linked List

  • 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 a 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 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 on how to Delete N nodes after M nodes of a Linked List

Code Implementation

#include <stdio.h>
#include <stdlib.h>
 
// A linked list node
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;
 
    new_node->next = (*head_ref);
 
    (*head_ref)  = new_node;
}
 
void printList(struct Node *head)
{
    struct Node *temp = head;
    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()
{
    struct Node* head = NULL;
    int M=2, N=3;
    push(&head, 10);
    push(&head, 9);
    push(&head, 8);
    push(&head, 7);
    push(&head, 6);
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);
 
    printf("M = %d, N = %d \nGiven Linked list is :\n", M, N);
    printList(head);
 
    skipMdeleteN(head, M, N);
 
    printf("\nLinked list after deletion is :\n");
    printList(head);
 
    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;

    new_node->next = (*head_ref);

    (*head_ref) = new_node;
}

void printList(Node *head)
{
    Node *temp = head;
    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()
{

    Node* head = NULL;
    int M=2, N=2;
    push(&head, 8);
    push(&head, 7);
    push(&head, 45);
    push(&head, 56);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);
    cout << "M = " << M<< " N = " << N << "\nGiven Linked list is :\n";
    printList(head);
 
    skipMdeleteN(head, M, N);
 
    cout<<"\nLinked list after deletion is :\n";
    printList(head);
 
    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;

    new_node.next = (head_ref);

    (head_ref) = new_node;
    
    return head_ref;
}

static void printList( Node head)
{
    Node temp = head;
    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)
{
    Node curr = head, t;
    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[])
{

    Node head = null;
    int M=2, N=2;
    head=push(head, 8);
    head=push(head, 7);
    head=push(head, 45);
    head=push(head, 56);
    head=push(head, 4);
    head=push(head, 3);
    head=push(head, 2);
    head=push(head, 1);
    System.out.printf("M = %d, N = %d \nGiven" +
                        "Linked list is :\n", M, N);
    printList(head);

    skipMdeleteN(head, M, N);

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

class LinkedList:

    def __init__(self):
        self.head = None

    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

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

    def skipMdeleteN(self, M, N):
        curr = self.head
        
        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

llist = LinkedList()
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()

Output

Given Linked list
1 2 3 4 56 45 7 8

Linked list after deletion
1 2 56 45

Time Complexity: O(n), as no nested traversal is needed.
Space Complexity: O(1), as only temporary variables are being created.

So, in this article, we have tried to explain the most efficient approach to delete N nodes after M nodes of a linked list. This is an important question when it comes to coding interviews. If you want to solve more questions on Linked List, which is curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Related Articles
Doubly circular linked list in data structure Application of doubly linked list
Applications of linked list Singly linked list vs doubly linked list
Advantages and disadvantages of linked list Doubly linked list all operations in C
Binary search in linked list Bubble sort linked list
Deletion in doubly linked list Delete the middle node of a linked list
Polynomial addition using linked list Find max value and min value in linked list
Insert a node at a specific position in a linked list Swap nodes in linked list
Add two numbers represented by linked lists Find starting point of loop in linked list
Merge sort linked list Delete a node from linked list at a given position
Remove duplicates from unsorted linked list Reverse a linked list in Python

FAQs

  1. How do you delete a node after a given node?

  2. To delete a node after a given node, we have to skip the desired number of nodes to reach the current node after which the node will be deleted. We need to keep track of the current node.

  3. How do you remove a node from a linked list in java?

  4. To delete a node from a linked list:

    • Find the previous node of a linked list.
    • Change the next pointer of the previous node.
    • Free the memory of the node to be deleted.

  5. What is deletion in a singly linked list?

  6. Deletion operation is one of the easiest operations of all, let’s say we have to remove the first node of the linked list we just need to make the head pointer to the next node.

Leave a Reply

Your email address will not be published. Required fields are marked *