Lecture 146:-Delete N Nodes After M Nodes

To delete N nodes after every M nodes in a singly linked list, you can follow these steps:

1. Traverse the linked list.
2. For each group of M nodes, traverse N nodes and keep track of the previous node.
3. Update the next pointer of the previous node to skip the N nodes.
4. Repeat this process until you reach the end of the list.

Here's a C++ implementation of this approach:

cppCopy code

#include <iostream> class Node { public: int data; Node* next; Node(int value) : data(value), next(nullptr) {} }; Node* deleteNMNodes(Node* head, int M, int N) { if (!head || M <= 0 || N <= 0) return head; Node* current = head; Node* prev = nullptr; while (current) { // Traverse M nodes for (int i = 0; i < M && current; ++i) { prev = current; current = current->next; } // Traverse N nodes and delete them for (int i = 0; i < N && current; ++i) { Node* temp = current; current = current->next; delete temp; } // Update previous node's next pointer prev->next = current; } return head; } void displayList(Node* head) { while (head) { std::cout << head->data << " "; head = head->next; } std::cout << std::endl; } int main() { Node* head = new Node(1); head->next = new Node(2); head->next->next = new Node(3); head->next->next->next = new Node(4); head->next->next->next->next = new Node(5); head->next->next->next->next->next = new Node(6); head->next->next->next->next->next->next = new Node(7); int M = 2; int N = 1; std::cout << "Original List: "; displayList(head); head = deleteNMNodes(head, M, N); std::cout << "List after deleting " << N << " nodes after every " << M << " nodes: "; displayList(head); return 0; }

In this example, the deleteNMNodes function deletes N nodes after every M nodes. The displayList function is used to display the original and modified lists.

The time complexity of this algorithm is O(N), where N is the number of nodes in the list. The space complexity is O(1).