Ta được cung cấp một danh sách liên kết đơn, và ta được giao nhiệm vụ xóa nút cuối cùng khỏi danh sách đó. Trong bài toán này, ta đơn giản sẽ duyệt qua danh sách cho trước và đơn giản xóa nút cuối cùng.
Phương pháp tìm giải pháp
Trong phương pháp này, ta đi qua danh sách cho trước, và ta theo dõi nút trước và nút hiện tại. Bây giờ khi nút hiện tại trở thành nút cuối cùng, ta thay đổi previous -> next thành NULL và xóa nút hiện tại.
Ví dụ
#include <iostream> using namespace std; struct Node { int data; struct Node* next; }; void push(struct Node** ref, int new_data) { // đẩy nút struct Node* new_n = new Node; new_n->data = new_data; new_n->next = (*ref); (*ref) = new_n; } int main() { Node* head = NULL; push(&head, 12); push(&head, 29); push(&head, 11); push(&head, 23); push(&head, 8); auto curr = head, prev = head; if (!curr || !curr -> next) // nếu danh sách chỉ có 1 phần tử hoặc rỗng cout << "Empty\n"; else { while (curr) { // trong khi curr != NULL if (!curr -> next) { prev -> next = NULL; delete(curr); // giải phóng không gian break; } prev = curr; curr = curr -> next; // chuyển đến nút tiếp theo } } for (Node* temp = head; temp != NULL; temp = temp->next) // in dữ liệu cout << temp->data << " "; return 0; }Kết quả
8 23 11 29
Giải thích mã trên
Trong phương pháp này, ta duyệt qua mảng, theo dõi nút hiện tại và nút trước. Bây giờ khi nút hiện tại trở thành nút cuối cùng, ta thay đổi previous -> next thành NULL và xóa nút hiện tại. Độ phức tạp thời gian tổng thể của chương trình cho trước là O(N), N là kích thước danh sách cho trước.
Độ phức tạp thời gian − O(N)
N: Kích thước mảng của ta
Kết luận
Trong bài viết này, ta giải quyết bài toán Xóa nút cuối cùng khỏi danh sách liên kết cho trước. Ta cũng học chương trình C++ cho bài toán này và phương pháp hoàn chỉnh ta đã giải quyết. Ta có thể viết cùng chương trình bằng ngôn ngữ khác như C, Java, Python và các ngôn ngữ khác. Hy vọng bạn thấy bài viết hữu ích.