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

โจทย์: ลบโหนดที่อยู่ตรงกลางของ Singly Linked List หากจำนวนโหนดเป็นคู่ ให้ลบโหนดกลางขวา (index n/2)

แนวคิด

1. นับจำนวนโหนดทั้งหมด
2. หาตำแหน่งกลาง: mid = count / 2
3. เดินไปยังโหนดก่อนกลาง (mid-1)
4. ข้ามโหนดกลางโดยเชื่อม prev->next = mid->next
5. ลบโหนดกลาง

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

#include <iostream>
using namespace std;

struct Node {
    int data;
    struct Node* next;
};

Node* createNode(int data) {
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

int nodeCount(struct Node* head) {
    int count = 0;
    while (head != NULL) {
        head = head->next;
        count++;
    }
    return count;
}

struct Node* deleteMiddle(struct Node* head) {
    if (head == NULL)
        return NULL;
    if (head->next == NULL) {
        delete head;
        return NULL;
    }
    
    Node* temphead = head;
    int count = nodeCount(head);
    int mid = count / 2;
    
    // เดินไปยังโหนดก่อนกลาง
    while (mid-- > 1) {
        head = head->next;
    }
    
    // ลบโหนดกลาง
    Node* toDelete = head->next;
    head->next = head->next->next;
    delete toDelete;
    
    return temphead;
}

void printList(Node *ptr) {
    while (ptr != NULL) {
        cout << ptr->data << "->";
        ptr = ptr->next;
    }
    cout << "NULL" << endl;
}

int main() {
    struct Node* head = createNode(2);
    head->next = createNode(4);
    head->next->next = createNode(6);
    head->next->next->next = createNode(8);
    head->next->next->next->next = createNode(10);
    
    cout << "Original linked list" << endl;
    printList(head);
    
    head = deleteMiddle(head);
    
    cout << endl << "After deleting the middle of the linked list" << endl;
    printList(head);
    return 0;
}

ผลลัพธ์

Original linked list
2->4->6->8->10->NULL
After deleting the middle of the linked list
2->4->8->10->NULL

หมายเหตุ: สามารถทำได้ใน One-pass ด้วยเทคนิค Slow/Fast Pointer (Tortoise and Hare) ซึ่งมีประสิทธิภาพมากกว่า