Xóa các nút thay thế trong danh sách liên kết đơn trong C++

Trong hướng dẫn này, chúng ta sẽ học cách xóa tất cả các nút nguyên tố từ một danh sách liên kết đơn.

Hãy xem các bước để giải quyết vấn đề.

• Viết struct với dữ liệu và con trỏ next.
• Viết hàm để chèn nút vào danh sách liên kết đơn.
• Khởi tạo danh sách liên kết đơn với dữ liệu giả.
• Lặp qua danh sách liên kết đơn.
• Xóa nút thay thế bằng cách duy trì nút trước đó.
• Viết hàm để xóa nút. Xem xét ba trường hợp sau khi xóa nút:
  • Nếu nút là nút đầu, thì di chuyển head đến nút tiếp theo.
  • Nếu nút là nút giữa, thì liên kết nút tiếp theo với nút trước đó.
  • Nếu nút là nút cuối, thì xóa liên kết của nút trước đó.

Ví dụ mã

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

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

void deleteAlternateNodes(Node *head) {
    if (head == NULL)
        return;
    
    Node *prev = head;
    Node *node = head->next;
    
    while (prev != NULL && node != NULL) {
        prev->next = node->next;
        free(node);
        prev = prev->next;
        
        if (prev != NULL) {
            node = prev->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 *node) {
    while (node != NULL) {
        cout << node->data << " -> ";
        node = node->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 liên kết trước khi xóa:" << endl;
    printLinkedList(head);
    
    deleteAlternateNodes(head);
    
    cout << "\nDanh sách liên kết sau khi xóa:" << endl;
    printLinkedList(head);
    
    return 0;
}

Đầu ra

Nếu bạn thực thi chương trình trên, bạn sẽ nhận được kết quả sau.

Danh sách liên kết trước khi xóa: 6 -> 5 -> 4 -> 3 -> 2 -> 1 ->
Danh sách liên kết sau khi xóa: 6 -> 4 -> 2 ->

Kết luận

Nếu bạn có bất kỳ thắc mắc nào trong hướng dẫn, hãy đề cập chúng trong phần bình luận.