ลบ N โหนดหลัง M โหนดใน Linked List ใน C++

บทนำ

โจทย์: ใน Linked List ให้เก็บ M โหนด แล้วลบ N โหนดถัดไป ทำซ้ำจนจบ List

ตัวอย่าง

M=1, N=2, List: 1→2→3→4→5→6→7→8→9 เก็บ 1, ลบ 2,3 → เก็บ 4, ลบ 5,6 → เก็บ 7, ลบ 8,9 ผลลัพธ์: 1→4→7

ขั้นตอนการแก้ปัญหา

1. เดินไป M-1 โหนด (เก็บ M โหนด)
2. จากนั้นลบ N โหนดถัดไป (เก็บ pointer ถัดไปไว้ก่อนลบ)
3. เชื่อมโหนดปัจจุบันกับโหนดหลังช่วงที่ลบ
4. ทำซ้ำจนจบ List

ตัวอย่างโค้ด

#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 != NULL) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "Null" << endl;
}

void deleteNNodesAfterMNodes(Node *head, int M, int N) {
    Node *current = head, *temp;
    int count;
    while (current) {
        for (count = 1; count < M && current != NULL; count++) {
            current = current->next;
        }
        if (current == NULL) return;
        temp = current->next;
        for (count = 1; count <= N && temp != NULL; count++) {
            Node *deletingNode = temp;
            temp = temp->next;
            free(deletingNode);
        }
        current->next = temp;
        current = temp;
    }
}

int main() {
    Node* head = NULL;
    int M = 1, N = 2;
    insertNode(&head, 1);
    insertNode(&head, 2);
    insertNode(&head, 3);
    insertNode(&head, 4);
    insertNode(&head, 5);
    insertNode(&head, 6);
    insertNode(&head, 7);
    insertNode(&head, 8);
    insertNode(&head, 9);
    cout << "Linked list before deletion: ";
    printLinkedList(head);
    deleteNNodesAfterMNodes(head, M, N);
    cout << "Linked list after deletion: ";
    printLinkedList(head);
    return 0;
}

ผลลัพธ์

Linked list before deletion: 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> Null
Linked list after deletion: 9 -> 6 -> 3 -> Null

หมายเหตุ

insertNode เพิ่มที่หัว (Head) ดังนั้นลำดับกลับกัน โค้ดทำงานถูกต้องตามตรรกะ M=1 N=2

สรุป

อัลกอริทึม O(n) เดินผ่าน List ครั้งเดียว ใช้ pointer manipulation ตรงจุด ไม่ต้อง allocate ใหม่