Elimina il nodo centrale di una lista concatenata

𝗘𝗹𝗶𝗺𝗶𝗻𝗮 𝗶𝗹 𝗻𝗼𝗱𝗼 𝗰𝗲𝗻𝘁𝗿𝗮𝗹𝗲 𝗱𝗶 𝘂𝗻𝗮 𝗹𝗶𝘀𝘁𝗮 𝗰𝗼𝗻𝗰𝗮𝘁𝗲𝗻𝗮𝘁𝗮

Devi rimuovere il nodo centrale da una lista concatenata singola. Il nodo centrale è l'⌊n / 2⌋-esimo nodo utilizzando un'indicizzazione basata su 0.

Ecco come risolverlo in modo efficiente.

La Strategia

Usa due puntatori per trovare il centro in un unico passaggio.

• Usa un puntatore lento che si muove di un passo alla volta.
• Usa un puntatore veloce che si muove di due passi alla volta.
• Quando il puntatore veloce raggiunge la fine, il puntatore lento si troverà al centro.
• Mantieni un terzo puntatore per tracciare il nodo precedente al puntatore lento.

La Logica

1. Gestisci il caso limite. Se la lista ha un solo nodo, restituisci null.
2. Inizializza i puntatori lento e veloce alla testa (head).
3. Sposta il puntatore veloce di due passi e il puntatore lento di un passo.
4. Aggiorna un puntatore prev per rimanere un passo dietro al puntatore lento.
5. Una volta terminato il ciclo, collega il nodo prev al nodo successivo a slow. In questo modo si salta il nodo centrale.

Complessità

• Complessità Temporale: O(n). Attraversi la lista una sola volta.
• Complessità Spaziale: O(1). Utilizzi solo tre puntatori.

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

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