Cho một danh sách liên kết, ta cần xóa phần tử đầu tiên và trả về con trỏ đến head của danh sách mới.
Input : 1 -> 2 -> 3 -> 4 -> 5 -> NULL Output : 2 -> 3 -> 4 -> 5 -> NULL Input : 2 -> 4 -> 6 -> 8 -> 33 -> 67 -> NULL Output : 4 -> 6 -> 8 -> 33 -> 67 -> NULL
Trong bài toán cho trước, ta cần xóa nút đầu tiên của danh sách và di chuyển head đến phần tử thứ hai và trả về head.
Phương pháp tìm giải pháp
Trong bài toán này, ta có thể di chuyển head đến vị trí tiếp theo và sau đó giải phóng nút trước.
Ví dụ
#include <iostream> using namespace std; /* Nút danh sách liên kết */ struct Node { int data; struct Node* next; }; void push(struct Node** head_ref, int new_data) { // đẩy dữ liệu vào danh sách struct Node* new_node = new Node; new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } int main() { Node* head = NULL; push(&head, 12); push(&head, 29); push(&head, 11); push(&head, 23); push(&head, 8); auto temp = head; // temp thành head head = head -> next; // head trở thành phần tử tiếp theo delete temp; // xóa temp tức là phần tử đầu tiên for (temp = head; temp != NULL; temp = temp->next) // in danh sách cout << temp->data << " "; return 0; }Kết quả
23 11 29 12
Giải thích mã trên
Trong chương trình này ta chỉ cần dịch head sang phần tử tiếp theo và xóa phần tử trước đó và in danh sách mới. Độ phức tạp thời gian tổng thể của chương trình cho trước là O(1) nghĩa là chương trình không phụ thuộc vào đầu vào cho trước, và đây là độ phức tạp tốt nhất có thể đạt được.
Kết luận
Trong bài viết này, ta giải quyết bài toán Xóa nút đầu tiên của danh sách liên kết. 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.