Xóa tất cả các nút chẵn khỏi danh sách liên kết đôi 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 có giá trị chẵn khỏi một danh sách liên kết đôi (doubly linked list) bằng C++.

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

1. Định nghĩa cấu trúc Node với các thành phần: dữ liệu (data), con trỏ trước (prev) và con trỏ sau (next).
2. Viết hàm chèn nút vào danh sách liên kết đôi.
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 xem dữ liệu của nút hiện tại có phải số chẵn hay không.
5. Nếu là số chẵn, xóa nút đó.
6. Viết hàm xóa nút, xử lý 3 trường hợp:
   • Nút là nút đầu (head): di chuyển head sang nút tiếp theo.
   • Nút là nút giữa: liên kết nút trước với nút sau.
   • Nút là nút cuối: xóa liên kết của nút trước.

Mã nguồn ví dụ

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

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

void insertNode(Node** head_ref, int new_data) {
    Node* new_node = (Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->prev = NULL;
    new_node->next = (*head_ref);
    if ((*head_ref) != NULL) {
        (*head_ref)->prev = new_node;
    }
    (*head_ref) = new_node;
}

void deleteNode(Node** head_ref, Node* del) {
    if (*head_ref == NULL || del == NULL) return;
    if (*head_ref == del) *head_ref = del->next;
    if (del->next != NULL) del->next->prev = del->prev;
    if (del->prev != NULL) del->prev->next = del->next;
    free(del);
}

void deleteEvenNodes(Node** head_ref) {
    Node* temp = *head_ref;
    Node* next;
    while (temp != NULL) {
        next = temp->next;
        if (temp->data % 2 == 0) {
            deleteNode(head_ref, temp);
        }
        temp = 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);
    deleteEvenNodes(&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 -> 1 ->

Kết luận

Chương trình đã xóa thành công tất cả các nút có giá trị chẵn khỏi danh sách liên kết đôi. Nếu bạn có thắc mắc, hãy để lại bình luận bên dưới.