ในบทช่วยสอนนี้ เราจะเรียนรู้วิธีลบโหนดกลางในรายการที่เชื่อมโยง
วิธีแก้ปัญหาตรงไปตรงมา เราจะมีตัวชี้สองตัว ตัวหนึ่งย้ายหนึ่งโหนดในแต่ละครั้ง และอีกตัวหนึ่งย้ายสองโหนดในแต่ละครั้ง เมื่อตัวชี้ที่สองไปถึงโหนดสุดท้าย ตัวแรกจะอยู่ตรงกลางของรายการที่เชื่อมโยง
มาดูขั้นตอนการแก้ปัญหากัน
-
เขียน struct Node สำหรับโหนดรายการที่เชื่อมโยง
-
เริ่มต้นรายการที่เชื่อมโยงด้วยข้อมูลจำลอง
-
เขียนฟังก์ชันเพื่อลบรายการที่เชื่อมโยง
-
เริ่มต้นตัวชี้สองตัว (ช้าและเร็ว) ด้วยตัวชี้ส่วนหัวของรายการที่เชื่อมโยง
-
วนซ้ำในรายการที่เชื่อมโยงจนกว่าตัวชี้แบบเร็วจะถึงจุดสิ้นสุด
-
ย้ายตัวชี้ช้าไปยังโหนดถัดไป
-
ย้ายตัวชี้แบบเร็วไปยังโหนดถัดไปของโหนดถัดไป
-
กลับหัวชี้
-
-
พิมพ์รายการที่เชื่อมโยง
ตัวอย่าง
มาดูโค้ดกันเลย
#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;
} ผลลัพธ์
หากคุณรันโปรแกรมข้างต้น คุณจะได้ผลลัพธ์ดังต่อไปนี้
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
บทสรุป
หากคุณมีข้อสงสัยใดๆ ในบทแนะนำ โปรดระบุในส่วนความคิดเห็น
