Xóa tất cả các nút không phải số nguyên tố khỏi danh sách liên kết đơn trong C++

Giới thiệu

Trong hướng dẫn này, chúng ta sẽ học cách xóa tất cả các nút không phải số nguyên tố (non-prime) khỏi một danh sách liên kết đơn, chỉ giữ lại các nút có giá trị là số nguyên tố.

Các bước thực hiện

1. Định nghĩa cấu trúc Node với dữ liệu và con trỏ next.
2. Viết hàm chèn nút vào danh sách.
3. Khởi tạo danh sách với dữ liệu mẫu.
4. Duyệt qua danh sách, kiểm tra mỗi nút: nếu không phải số nguyên tố thì xóa.
5. Viết hàm xóa tối ưu: xử lý riêng các nút đầu liên tiếp không phải số nguyên tố, sau đó duyệt các nút còn lại.

Mã nguồn ví dụ

#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;
}

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i = i + 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

void deleteNonPrimeNodes(Node** head_ref) {
    Node* ptr = *head_ref;
    // Xóa các nút đầu không phải số nguyên tố
    while (ptr != NULL && !isPrime(ptr->data)) {
        Node* temp = ptr;
        ptr = ptr->next;
        delete(temp);
    }
    *head_ref = ptr;
    if (ptr == NULL) return;

    Node* curr = ptr->next;
    while (curr != NULL) {
        if (!isPrime(curr->data)) {
            ptr->next = curr->next;
            delete(curr);
            curr = ptr->next;
        } else {
            ptr = curr;
            curr = curr->next;
        }
    }
}

void printLinkedList(Node* head) {
    while (head != NULL) {
        cout << head->data << " -> ";
        head = head->next;
    }
}

int main() {
    Node* head = NULL;
    insertNode(&head, 1);
    insertNode(&head, 2);
    insertNode(&head, 3);
    insertNode(&head, 4);
    insertNode(&head, 5);
    insertNode(&head, 6);
    cout << "Danh sách trước khi xóa:" << endl;
    printLinkedList(head);
    deleteNonPrimeNodes(&head);
    cout << "\nDanh sách sau khi xóa:" << endl;
    printLinkedList(head);
    return 0;
}

Kết quả đầu ra

Danh sách trước khi xóa: 6 -> 5 -> 4 -> 3 -> 2 -> 1 ->
Danh sách sau khi xóa: 5 -> 3 -> 2 ->

Kết luận

Chương trình giữ lại các nút số nguyên tố (2, 3, 5) và xóa các nút còn lại (1, 4, 6). Nếu bạn có thắc mắc, hãy để lại bình luận bên dưới.