Xóa N node sau M node trong danh sách liên kết C++

Giới thiệu

Cho danh sách liên kết đơn, xóa N node sau mỗi M node. Lặp lại cho đến hết danh sách.

Ví dụ

Danh sách: 1→2→3→4→5→6→7→8→9

M=1, N=2: Giữ 1, xóa 2,3 | Giữ 4, xóa 5,6 | Giữ 7, xóa 8,9

Kết quả: 1→4→7

Mã nguồn hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* next;
};

void insertNode(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 printLinkedList(Node* head) {
    Node* temp = head;
    while (temp) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL" << endl;
}

void deleteNNodesAfterMNodes(Node* head, int M, int N) {
    Node* current = head;
    
    while (current) {
        // Bỏ qua M node
        for (int count = 1; count < M && current != NULL; count++) {
            current = current->next;
        }
        
        if (!current) return; // Hết danh sách
        
        // Xóa N node tiếp theo
        Node* temp = current->next;
        for (int count = 1; count <= N && temp != NULL; count++) {
            Node* del = temp;
            temp = temp->next;
            delete del;
        }
        
        // Nối current với node sau N node đã xóa
        current->next = temp;
        current = temp;
    }
}

int main() {
    Node* head = NULL;
    int M = 1, N = 2;
    
    // Tạo danh sách 1->2->3->4->5->6->7->8->9
    for (int i = 9; i >= 1; i--) insertNode(&head, i);
    
    cout << "Truoc khi xoa: ";
    printLinkedList(head);
    
    deleteNNodesAfterMNodes(head, M, N);
    
    cout << "Sau khi xoa: ";
    printLinkedList(head);
    
    return 0;
}

Kết quả chạy chương trình

Truoc khi xoa: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> NULL
Sau khi xoa: 1 -> 4 -> 7 -> NULL

Phân tích độ phức tạp

• Thời gian: O(n) - mỗi node được thăm tối đa 1 lần
• Không gian: O(1) - chỉ dùng con trỏ

Các trường hợp đặc biệt

• M = 0: Xóa N node đầu tiên, sau đó lặp lại (xóa tất cả nếu N > 0)
• N = 0: Không xóa gì, danh sách không đổi
• M = 1, N = 1: Giữ 1, xóa 1, giữ 1, xóa 1... (giữ các node lẻ)
• Danh sách rỗng: Không làm gì

Biến thể: Xóa N node sau M node (đếm từ 0)

Nếu M=0 nghĩa là xóa ngay từ đầu. Code trên giả định M≥1 (giữ ít nhất 1 node trước khi xóa).

Kết luận

Kỹ thuật two-pointer (current + temp) duyệt và xóa node trong danh sách liên kết. Cần cẩn thận cập nhật con trỏ next và giải phóng bộ nhớ (delete).