Hapus Node Tengah dari Sebuah Linked List

𝗗𝗲𝗹𝗲𝘁𝗲 𝘁𝗵𝗲 𝗠𝗶𝗱𝗱𝗹𝗲 𝗡𝗼𝗱𝗲 𝗼𝗳 𝗮 𝗟𝗶𝗻𝗸𝗲𝗱 𝗟𝗶𝘀𝘁 -> Hapus Node Tengah dari Linked List

Anda perlu menghapus node tengah dari sebuah singly linked list. Node tengah adalah node ke-⌊n / 2⌋ menggunakan pengindeksan berbasis 0.

Berikut adalah cara menyelesaikannya secara efisien.

The Strategy -> Strategi

Gunakan dua pointer untuk menemukan bagian tengah dalam satu kali iterasi.

• Gunakan slow pointer yang bergerak satu langkah setiap waktu.
• Gunakan fast pointer yang bergerak dua langkah setiap waktu.
• Ketika fast pointer mencapai akhir, slow pointer akan berada di tengah.
• Gunakan pointer ketiga untuk melacak node sebelum slow pointer.

The Logic -> Logika

1. Tangani kasus tepi (edge case). Jika list hanya memiliki satu node, kembalikan null.
2. Inisialisasi slow dan fast pointer pada head.
3. Gerakkan fast pointer dua langkah dan slow pointer satu langkah.
4. Perbarui pointer prev agar tetap satu langkah di belakang slow pointer.
5. Setelah loop berakhir, hubungkan node prev ke node setelah slow. Ini akan melewati node tengah.

Complexity -> Kompleksitas

• Kompleksitas Waktu: O(n). Anda menelusuri list satu kali.
• Kompleksitas Ruang: O(1). Anda hanya menggunakan tiga pointer.

PHP Implementation -> Implementasi 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;
}

Source: https://dev.to/mdarifulhaque/2095-delete-the-middle-node-of-a-linked-list-4jf1