Trong bài viết này, chúng tôi sẽ giải thích cách loại bỏ mọi nút thứ k của danh sách liên kết. Chúng ta phải xóa mọi nút nằm trên bội số của k, tức là chúng ta phải xóa nút trên các 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 Explanation: As 3 is the k-th node after its deletion list would be : First iteration :112->231->41->54->63->71->85 Now we count from 41 the next kth node is 63 After the second iteration our list will become : 112->231->41->54->71->85 And our iteration continues like this. Input: 14->21->23->54->56->61 k = 1 Output: Empty list Explanation: All nodes need to be deleted
Trong vấn đề này, chúng tôi sẽ áp dụng một cách tiếp cận thông thường đủ hiệu quả để chúng tôi không cần tối ưu hóa nó.
Phương pháp tiếp cận để tìm ra giải pháp
Trong bài toán này, chúng ta sẽ duyệt qua danh sách được liên kết với một bộ đếm. Nếu bộ đếm chạm đến k, chúng tôi xóa nút đó và làm mới bộ đếm để tìm phần tử tiếp theo ở vị trí thứ k từ nút hiện tại.
Ví dụ
#include<bits/stdc++.h>
using namespace std;
/* Linked list Node */
struct Node {
int data;
struct Node* next;
};
void push(struct Node** ref, int new_data) { // pushing the data into the list
struct Node* new_n = new Node;
new_n->data = new_data;
new_n->next = (*ref);
(*ref) = new_n;
}
void deletek(Node* prev, Node* curr) { // delete function
if(prev == NULL) {
prev = curr;
curr = curr -> next;
free(prev);
prev = NULL;
} else {
prev -> next = curr -> next;
auto tmp = curr;
free(tmp); // freeing the space
}
}
/* Function to print linked list */
void displayList(struct Node *head) {
struct Node *temp = head;
while (temp != NULL) {
cout<<temp->data<<" ";
temp = temp->next;
}
}
// Function to create a new node.
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; // given k
Node* curr = head; // current pointer
Node* prev = NULL; // previous pointer
int count = 1; // position counter
if(head == NULL || k == 0) // if list is already empty or k = 0
cout << "Invalid\n";
else {
while(curr) { // traversing the list
if(count == k) {
deletek(prev, curr);
curr = prev -> next;
count = 1;
} else {
count++;
prev = curr;
curr = curr -> next;
}
}
displayList(head); // printing the new list
}
return 0;
} Đầu ra
20 30 50 60 80
Phương pháp trên có độ phức tạp về thời gian là O (N) , trong đó N là kích thước của danh sách liên kết đã cho của chúng tôi.
Giải thích về đoạn mã trên
Trong cách tiếp cận trên, đầu tiên chúng ta giữ ba thứ trong tay, con trỏ hiện tại, thứ hai là con trỏ trước đó và thứ ba là bộ đếm vị trí. Bây giờ chúng ta xóa một số nút khi bộ đếm vị trí của chúng ta trở nên bằng nhau để biết rằng chúng ta gọi hàm xóa với bộ đếm trước đó và bộ đếm hiện tại vì các tham số bây giờ chúng ta xóa nút hiện tại và giải phóng dung lượng ngay bây giờ khi chức năng xóa được thực hiện. Bây giờ chúng ta chuyển con trỏ hiện tại sang phần tử tiếp theo và làm mới bộ đếm của chúng tôi thành 1 và lặp lại khối này cho đến khi khối hiện tại của chúng tôi trở thành NULL.
Kết luận
Trong bài viết này, chúng tôi giải quyết vấn đề Xóa mọi nút thứ k của danh sách liên kết. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy bài viết này hữu ích.