Padam Nod Tengah dalam Senarai Berpautan

Padamkan Nod Tengah dalam Senarai Berpautan

Anda perlu membuang nod tengah daripada senarai berpautan tunggal (singly linked list). Nod tengah ialah nod ke-⌊n / 2⌋ menggunakan pengindeksan berasaskan 0.

Berikut adalah cara untuk menyelesaikannya dengan cekap.

Strategi

Gunakan dua penunjuk (pointer) untuk mencari bahagian tengah dalam satu laluan.

• Gunakan penunjuk perlahan (slow pointer) yang bergerak satu langkah pada satu masa.
• Gunakan penunjuk pantas (fast pointer) yang bergerak dua langkah pada satu masa.
• Apabila penunjuk pantas sampai ke penghujung, penunjuk perlahan akan berada di tengah.
• Simpan penunjuk ketiga untuk menjejaki nod sebelum penunjuk perlahan.

Logik

1. Kendalikan kes hujung (edge case). Jika senarai hanya mempunyai satu nod, pulangkan null.
2. Mulakan penunjuk perlahan dan pantas pada 'head'.
3. Gerakkan penunjuk pantas sebanyak dua langkah dan penunjuk perlahan sebanyak satu langkah.
4. Kemas kini penunjuk prev supaya sentiasa berada satu langkah di belakang penunjuk perlahan.
5. Sebaik sahaja gelung (loop) tamat, hubungkan nod prev ke nod selepas slow. Ini akan melangkau nod tengah tersebut.

Kompleksiti

• Kompleksiti Masa: O(n). Anda menelusuri senarai tersebut sekali sahaja.
• Kompleksiti Ruang: O(1). Anda hanya menggunakan tiga penunjuk.

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;
}

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