𝗗𝗲𝗹𝗲𝘁𝗲 𝘁𝗵𝗲 𝗠𝗶𝗱𝗱𝗹𝗲 𝗡𝗼𝗱𝗲 𝗼𝗳 𝗮 𝗟𝗶𝗻𝗸𝗲𝗱 𝗟𝗶𝘀𝘁

การลบโหนดกลางของ Linked List

คุณต้องลบโหนดกลางออกจาก singly linked list โดยโหนดกลางคือโหนดลำดับที่ ⌊n / 2⌋ เมื่อใช้การนับดัชนีแบบเริ่มจาก 0 (0-based indexing)

นี่คือวิธีการแก้ปัญหานี้อย่างมีประสิทธิภาพ

กลยุทธ์

ใช้ pointer สองตัวเพื่อหาจุดกึ่งกลางในการวนลูปเพียงรอบเดียว

• ใช้ slow pointer ที่เคลื่อนที่ทีละหนึ่งก้าว
• ใช้ fast pointer ที่เคลื่อนที่ทีละสองก้าว
• เมื่อ fast pointer ไปถึงจุดสิ้นสุด slow pointer จะอยู่ที่ตำแหน่งกึ่งกลางพอดี
• ใช้ pointer ตัวที่สามเพื่อติดตามโหนดที่อยู่ก่อนหน้า slow pointer

ตรรกะการทำงาน

1. จัดการกรณีขอบเขต (edge case): หากรายการมีเพียงโหนดเดียว ให้คืนค่า null
2. กำหนดค่าเริ่มต้นให้ slow และ fast pointer ที่ head
3. เคลื่อนที่ fast pointer ไปสองก้าว และ slow pointer ไปหนึ่งก้าว
4. อัปเดตตัวชี้ prev ให้ตามหลัง slow pointer อยู่หนึ่งก้าวเสมอ
5. เมื่อสิ้นสุดการวนลูป ให้เชื่อมต่อโหนด prev เข้ากับโหนดที่อยู่ถัดจาก slow ซึ่งจะเป็นการข้ามโหนดกลางไป

ความซับซ้อน

• Time Complexity: O(n). คุณวนลูปผ่านรายการเพียงรอบเดียว
• Space Complexity: O(1). คุณใช้เพียง pointer สามตัวเท่านั้น

การเขียนโปรแกรมด้วย PHP

function deleteMiddle(ListNode $head): ?ListNode
{
    if ($head->next == null) {
        return null;
    }

    $slow = $head;
    $fast = $head;
    $prev = null;

    while ($fast !== null && $fast->next !== null) {
        $prev = $slow;
        $slow = $slow->next;
        $fast = $fast->next->next;
    }

    $prev->next = $slow->next;

    return $head;
}

ที่มา: https://dev.to/mdarifulhaque/2095-delete-the-middle-node-of-a-linked-list-4jf1