Delete Node in a Linked List - C++ Solution

1. Introduction

This blog post demonstrates how to manipulate a singly-linked list in C++ by deleting certain nodes based on given criteria. The task involves skipping m nodes and then deleting the next n nodes in a singly-linked list.

Problem

Given a singly-linked list and two positive numbers, m and n, the task is to delete every n nodes in the list after skipping m nodes.

Examples:

- Input: List: 1 —> 2 —> 3 —> 4 —> 5 —> 6 —> 7 —> 8 —> 9 —> 10 —> nullptr, m = 1, n = 3

Output: 1 —> 5 —> 9 —> nullptr

- Input: List: 1 —> 2 —> 3 —> 4 —> 5 —> 6 —> 7 —> 8 —> 9 —> 10 —> nullptr, m = 2, n = 2

Output: 1 —> 2 —> 5 —> 6 —> 9 —> 10 —> nullptr

2. Solution Steps

1. Iterate through the linked list.

2. Skip m nodes.

3. Delete the next n nodes.

4. Repeat steps 2 and 3 until the end of the list.

5. Handle edge cases where the list ends before completing the deletions.

3. Code Program

#include <iostream>
using namespace std;

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

// Function to delete n nodes after skipping m nodes
ListNode* deleteNodes(ListNode* head, int m, int n) {
    ListNode *current = head, *temp;
    int count;

    while (current) {
        // Skip m nodes
        for (count = 1; count < m && current != nullptr; count++) {
            current = current->next;
        }

        // Delete n nodes
        if (current == nullptr) break;
        temp = current->next;
        for (count = 1; count <= n && temp != nullptr; count++) {
            ListNode *toDelete = temp;
            temp = temp->next;
            delete toDelete;
        }
        current->next = temp;
        current = temp;
    }

    return head;
}

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

int main() {
    // Creating a linked list
    ListNode* head = new ListNode(1);
    ListNode* current = head;
    for (int i = 2; i <= 10; i++) {
        current->next = new ListNode(i);
        current = current->next;
    }

    int m = 1, n = 3;
    head = deleteNodes(head, m, n);
    printLinkedList(head);
    return 0;
}

Output:

1 —> 5 —> 9 —> nullptr

Explanation:

The deleteNodes function handles the deletion of n nodes after skipping m nodes in the linked list. It iterates through the list, first skipping m nodes, and then deletes the next n nodes, taking care to handle cases where the list ends before all deletions are completed. The function returns the modified head of the list. The main function demonstrates the process with an example, creating a list and then modifying it according to the specified rules.