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

Futa Node ya Kati ya Linked List

Unahitaji kuondoa node ya kati kutoka kwenye singly linked list. Node ya kati ni node ya ⌊n / 2⌋-th kwa kutumia mfumo wa kuanzia 0 (0-based indexing).

Hivi ndivyo unavyoweza kuitatua kwa ufanisi.

Mkakati

Tumia viashiria (pointers) viwili ili kupata katikati kwa hatua moja.

• Tumia slow pointer inayotembea hatua moja kwa wakati mmoja.
• Tumia fast pointer inayotembea hatua mbili kwa wakati mmoja.
• Fast pointer inapofika mwisho, slow pointer itakuwa imefika katikati.
• Weka kiashiria (pointer) cha tatu ili kufuatilia node iliyo kabla ya slow pointer.

Mantiki

1. Shughulikia hali ya kipekee (edge case). Ikiwa orodha ina node moja tu, rudisha null.
2. Anzisha slow na fast pointers kwenye kichwa (head).
3. Sogeza fast pointer hatua mbili na slow pointer hatua moja.
4. Sasisha prev pointer ili ibaki hatua moja nyuma ya slow pointer.
5. Baada ya mzunguko (loop) kuisha, unganisha prev node na node iliyo baada ya slow. Hii itairuka node ya kati.

Ugumu (Complexity)

• Time Complexity: O(n). Unapitia orodha mara moja tu.
• Space Complexity: O(1). Unatumia viashiria (pointers) vitatu pekee.

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

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