Delete N Nodes After M Nodes of a Linked List - CPP Solution

1. Introduction

This blog post focuses on a specific linked list manipulation problem: deleting a certain number of nodes after a specified number of nodes in a singly linked list. This task combines elements of linked list traversal and conditional node deletion.

Problem

Given the head of a singly linked list, we need to delete N nodes after every M nodes of the linked list.

2. Solution Steps

1. Traverse the linked list using a loop.

2. Skip M nodes.

3. Delete the next N nodes after the M nodes.

4. Continue this process until the end of the list.

3. Code Program

#include <iostream>
using namespace std;

// ListNode structure definition
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to delete N nodes after M nodes of the list
void deleteNodes(ListNode* head, int M, int N) {
    ListNode *current = head, *temp;
    while (current) {
        for (int i = 1; i < M && current != nullptr; i++) {
            current = current->next;
        }

        if (current == nullptr) break;

        temp = current->next;
        for (int i = 0; i < N && temp != nullptr; i++) {
            ListNode* toDelete = temp;
            temp = temp->next;
            delete toDelete;
        }

        current->next = temp;
        current = temp;
    }
}

// Function to print the linked list
void printList(ListNode* head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "nullptr\n";
}

int main() {
    // Creating a linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    head->next->next->next->next->next = new ListNode(6);
    head->next->next->next->next->next->next = new ListNode(7);
    head->next->next->next->next->next->next->next = new ListNode(8);

    deleteNodes(head, 2, 2);
    printList(head); // Expected output: 1 -> 2 -> 5 -> 6 -> nullptr
    return 0;
}

Output:

1 -> 2 -> 5 -> 6 -> nullptr

Explanation:

The deleteNodes function modifies the given linked list by removing N nodes after every M nodes. 

It first traverses M nodes, then proceeds to delete the next N nodes, updating the next pointers accordingly. 

This process is repeated until the end of the list is reached. The function ensures that the specified number of nodes are skipped and then deleted as per the problem statement while maintaining the integrity of the remaining list.