Trong hướng dẫn này, chúng ta sẽ tìm hiểu cách xóa nút giữa trong danh sách được liên kết.
Giải pháp cho vấn đề rất đơn giản. Chúng ta sẽ có hai con trỏ, một con trỏ di chuyển một nút tại một thời điểm và con trỏ kia di chuyển hai nút tại một thời điểm. Vào thời điểm con trỏ thứ hai đến nút cuối cùng, con trỏ đầu tiên sẽ ở giữa danh sách được liên kết.
Hãy xem các bước để giải quyết vấn đề.
-
Viết một nút cấu trúc cho nút danh sách liên kết.
-
Khởi tạo danh sách được liên kết với dữ liệu giả.
-
Viết một hàm để xóa danh sách liên kết.
-
Khởi tạo con trỏ hai (chậm và nhanh) bằng con trỏ đầu danh sách được liên kết.
-
Lặp lại danh sách được liên kết cho đến khi con trỏ nhanh đến cuối.
-
Di chuyển con trỏ chậm đến một nút tiếp theo.
-
Di chuyển con trỏ nhanh đến nút tiếp theo của nút tiếp theo.
-
Trả lại con trỏ đầu trang
-
-
In danh sách được liên kết.
Ví dụ
Hãy xem mã.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
struct Node* deleteMiddleNode(struct Node* head) {
if (head == NULL) {
return NULL;
}
if (head->next == NULL) {
delete head;
return NULL;
}
struct Node* slow_ptr = head;
struct Node* fast_ptr = head;
struct Node* prev;
while (fast_ptr != NULL && fast_ptr->next != NULL) {
fast_ptr = fast_ptr->next->next;
prev = slow_ptr;
slow_ptr = slow_ptr->next;
}
prev->next = slow_ptr->next;
delete slow_ptr;
return head;
}
void printLinkedList(struct Node* node) {
while (node != NULL) {
cout << node->data << " -> ";
node = node->next;
}
cout << "Null" << endl;
}
Node* newNode(int data) {
struct Node* temp = new Node;
temp->data = data;
temp->next = NULL;
return temp;
}
int main() {
struct Node* head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(3);
head->next->next->next = newNode(4);
head->next->next->next->next = newNode(5);
head->next->next->next->next->next = newNode(6);
cout << "Linked list before deleting middle node: ";
printLinkedList(head);
head = deleteMiddleNode(head);
cout << "Linked List after deleting middle node: ";
printLinkedList(head);
return 0;
} Đầu ra
Nếu bạn thực hiện chương trình trên, bạn sẽ nhận được kết quả sau.
Linked list before deleting middle node: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> Null Linked List after deleting middle node: 1 -> 2 -> 3 -> 5 -> 6 -> Null
Kết luận
Nếu bạn có bất kỳ câu hỏi nào trong hướng dẫn, hãy đề cập đến chúng trong phần bình luận.