ลบโหนดกลางของ Linked List ใน C++

บทนำ

ลบโหนดกลาง (Middle Node) ของ Linked List ใช้เทคนิค Two Pointers (Slow & Fast)

หลักการ Two Pointers

• Slow pointer เดินทีละ 1 โหนด
• Fast pointer เดินทีละ 2 โหนด
• เมื่อ Fast ถึงท้าย Slow จะอยู่ตรงกลาง
• ต้องเก็บ Previous ของ Slow ไว้เพื่อตัดลิงก์

ขั้นตอนการแก้ปัญหา

1. ถ้า List ว่างหรือมี 1 โหนด → ลบและคืน NULL
2. กำหนด slow, fast, prev = head
3. วนลูป while fast และ fast->next ไม่เป็น NULL
4. fast = fast->next->next, prev = slow, slow = slow->next
5. prev->next = slow->next (ตัด slow ออก)
6. delete slow

ตัวอย่างโค้ด

#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

คำอธิบาย

6 โหนด → โหนดกลางคือโหนดที่ 3 (ค่า 3) หรือโหนดที่ 4 (ค่า 4) ขึ้นอยู่กับนิยาม โค้ดนี้ลบโหนดที่ 4 (ค่า 4) เพราะ fast pointer เลี้ยวหน่อย

สรุป

Two Pointer Technique เป็นเทคนิคคลาสสิกสำหรับ Linked List ใช้ได้กับหาจุดกลาง, หาวงจร, หาจุดตัดของสอง List