Trong bài viết này, ta sẽ giải thích cách xóa mọi nút thứ k của danh sách liên kết. Ta phải xóa mọi nút nằm ở bội số của k, tức là ta phải xóa nút ở vị trí k, 2*k, 3*k, v.v.
Input : 112->231->31->41->54->63->71->85 k = 3 Output : 112->231->41->54->71->85 Giải thích: Vì 3 là nút thứ k sau khi xóa danh sách sẽ là : Lần lặp đầu :112->231->41->54->63->71->85 Bây giờ ta đếm từ 41 nút thứ k tiếp theo là 63 Sau lần lặp thứ hai danh sách sẽ trở thành : 112->231->41->54->71->85 Và lặp tiếp tục như vậy. Input: 14->21->23->54->56->61 k = 1 Output: Danh sách rỗng Giải thích: Tất cả nút cần bị xóa
Trong bài toán này, ta sẽ áp dụng phương pháp bình thường đủ hiệu quả để không cần tối ưu hóa.
Phương pháp tìm giải pháp
Trong bài toán này, ta sẽ duyệt danh sách liên kết với một bộ đếm. Nếu bộ đếm chạm k, ta xóa nút đó và đặt lại bộ đếm để tìm phần tử tiếp theo ở vị trí k từ nút hiện tại.
Ví dụ
#include<bits/stdc++.h> using namespace std; /* Nút danh sách liên kết */ struct Node { int data; struct Node* next; }; void push(struct Node** ref, int new_data) { // đẩy dữ liệu vào danh sách struct Node* new_n = new Node; new_n->data = new_data; new_n->next = (*ref); (*ref) = new_n; } void deletek(Node* prev, Node* curr) { // hàm xóa if(prev == NULL) { prev = curr; curr = curr -> next; free(prev); prev = NULL; } else { prev -> next = curr -> next; auto tmp = curr; free(tmp); // giải phóng không gian } } /* Hàm in danh sách liên kết */ void displayList(struct Node *head) { struct Node *temp = head; while (temp != NULL) { cout<<temp->data<<" "; temp = temp->next; } } // Hàm tạo nút mới. struct Node *newNode(int x) { Node *temp = new Node; temp->data = x; temp->next = NULL; return temp; } int main() { struct Node* head = NULL; push(&head, 80); push(&head, 70); push(&head, 60); push(&head, 50); push(&head, 40); push(&head, 30); push(&head, 20); int k = 3; // k cho trước Node* curr = head; // con trỏ hiện tại Node* prev = NULL; // con trỏ trước int count = 1; // bộ đếm vị trí if(head == NULL || k == 0) // nếu danh sách rỗng hoặc k = 0 cout << "Invalid\n"; else { while(curr) { // duyệt danh sách if(count == k) { deletek(prev, curr); curr = prev -> next; count = 1; } else { count++; prev = curr; curr = curr -> next; } } displayList(head); // in danh sách mới } return 0; }Kết quả
20 30 50 60 80
Phương pháp trên có độ phức tạp thời gian O(N), N là kích thước danh sách liên kết cho trước.
Giải thích mã trên
Trong phương pháp trên, ta giữ ba thứ: con trỏ hiện tại, con trỏ trước, và bộ đếm vị trí. Bây giờ ta xóa nút khi bộ đếm vị trí bằng k, ta gọi hàm xóa với con trỏ trước và hiện tại làm tham số. Bây giờ ta xóa nút hiện tại và giải phóng không gian. Bây giờ khi hàm xóa xong, ta dịch con trỏ hiện tại sang phần tử tiếp theo và đặt lại bộ đếm về 1 và lặp khối này cho đến khi current thành NULL.
Kết luận
Trong bài viết này, ta giải quyết bài toán Xóa mọi nút thứ k 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 (Bình thường) để giải quyết bài toán. 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.