Xóa nút khỏi danh sách liên kết đơn không cần con trỏ head trong C++

Giới thiệu

Trong hướng dẫn này, chúng ta sẽ học cách xóa một nút trong danh sách liên kết đơn không có con trỏ head - chỉ được cho con trỏ trỏ trực tiếp đến nút cần xóa.

Ý tưởng chính

Vì không có con trỏ head để truy cập nút trước, ta không thể gán prev->next = del->next. Thay vào đó, ta sao chép dữ liệu từ nút tiếp theo vào nút hiện tại, sau đó xóa nút tiếp theo.

Lưu ý: Kỹ thuật này không hoạt động nếu nút cần xóa là nút cuối cùng (vì không có nút tiếp theo để sao chép).

Mã nguồn ví dụ

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

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

void deleteNodeWithoutHead(struct Node* deletingNode) {
    if (deletingNode == NULL) return;
    if (deletingNode->next == NULL) {
        cout << "Không thể xóa nút cuối không có head" << endl;
        return;
    }
    struct Node* temp = deletingNode->next;
    deletingNode->data = temp->data;
    deletingNode->next = temp->next;
    free(temp);
}

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

void insertNode(struct Node** head_ref, int new_data) {
    struct Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

int main() {
    struct 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);
    Node* del = head->next; // Nút thứ 2 (giá trị 5)
    deleteNodeWithoutHead(del);
    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: 6 -> 4 -> 3 -> 2 -> 1 ->

Kết luận

Kỹ thuật "copy next node" cho phép xóa nút trong O(1) thời gian mà không cần head, nhưng không áp dụng được cho nút cuối. Nếu bạn có thắc mắc, hãy để lại bình luận bên dưới.