Remova o Nó Central de uma Lista Encadeada

Remova o Nó Central de uma Lista Encadeada

Você precisa remover o nó central de uma lista encadeada simples. O nó central é o ⌊n / 2⌋-ésimo nó usando indexação baseada em 0.

Veja como resolvê-lo de forma eficiente.

A Estratégia

Use dois ponteiros para encontrar o meio em uma única passagem.

• Use um ponteiro lento que se move um passo por vez.
• Use um ponteiro rápido que se move dois passos por vez.
• Quando o ponteiro rápido chegar ao fim, o ponteiro lento estará no meio.
• Mantenha um terceiro ponteiro para rastrear o nó anterior ao ponteiro lento.

A Lógica

1. Trate o caso de borda. Se a lista tiver apenas um nó, retorne null.
2. Inicialize os ponteiros lento e rápido no head.
3. Mova o ponteiro rápido dois passos e o ponteiro lento um passo.
4. Atualize um ponteiro prev para permanecer um passo atrás do ponteiro lento.
5. Assim que o loop terminar, conecte o nó prev ao nó após o slow. Isso pula o nó central.

Complexidade

• Complexidade de Tempo: O(n). Você percorre a lista uma vez.
• Complexidade de Espaço: O(1). Você usa apenas três ponteiros.

Implementação em 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