Xóa tất cả các nút lớn hơn giá trị cho trước khỏi danh sách liên kết đôi 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 đôi.

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

• Viết struct với dữ liệu, con trỏ prev và next.
• Viết hàm để chèn nút vào danh sách liên kết đôi.
• Khởi tạo danh sách liên kết đôi với dữ liệu giả.
• Lặp qua danh sách liên kết đôi. Tìm xem dữ liệu nút hiện tại có lớn hơn giá trị cho trước hay không.
• Nếu dữ liệu hiện tại lớn hơn giá trị cho trước, thì xóa nút.
• 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 *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);
    return;
}

void deleteGreaterNode(Node** head_ref, int K) {
    Node* temp = *head_ref;
    Node* next;
    
    while (temp != NULL) {
        next = temp->next;
        
        if (temp->data > K) {
            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, 10);
    insertNode(&head, 11);
    insertNode(&head, 12);
    
    int K = 10;
    
    cout << "Danh sách liên kết trước khi xóa:" << endl;
    printLinkedList(head);
    
    deleteGreaterNode(&head, K);
    
    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: 12 -> 11 -> 10 -> 4 -> 3 -> 2 -> 1 ->
Danh sách liên kết sau khi xóa: 10 -> 4 -> 3 -> 2 -> 1 ->

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.