Xóa nút tại vị trí cho trước trong danh sách liên kết đơn 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 tại vị trí xác định (position) trong danh sách liên kết đơn.

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. Xác định vị trí cần xóa (đếm từ 1).
5. Duyệt đến nút ngay trước vị trí cần xóa.
6. Xử lý 3 trường hợp:
   • Vị trí 1 (head): cập nhật head sang nút tiếp theo.
   • Vị trí giữa: liên kết nút trước với nút sau nút bị xóa.
   • Vị trí cuối: nút trước trỏ sang NULL.
   • Vị trí không hợp lệ: không làm gì.

Mã nguồn ví dụ

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

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

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

void deleteNode(struct Node **head_ref, int position) {
    if (*head_ref == NULL) return;
    struct Node* temp = *head_ref;
    if (position == 1) {
        *head_ref = temp->next;
        free(temp);
        return;
    }
    for (int i = 2; temp != NULL && i < position - 1; i++) {
        temp = temp->next;
    }
    if (temp == NULL || temp->next == NULL) return;
    struct Node *next = temp->next->next;
    free(temp->next);
    temp->next = next;
}

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

int main() {
    struct Node* head = NULL;
    insertNode(&head, 1);
    insertNode(&head, 2);
    insertNode(&head, 3);
    insertNode(&head, 4);
    insertNode(&head, 5);
    cout << "Danh sách trước khi xóa:" << endl;
    printLinkedList(head);
    deleteNode(&head, 1); // Xóa vị trí 1 (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: 5->4->3->2->1->
Danh sách sau khi xóa: 4->3->2->1->

Kết luận

Hàm deleteNode xóa đúng nút tại vị trí cho trước, xử lý đầy đủ các trường hợp biên. Nếu bạn có thắc mắc, hãy để lại bình luận bên dưới.