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

Löschen des mittleren Knotens einer verketteten Liste

Sie müssen den mittleren Knoten aus einer einfach verketteten Liste entfernen. Der mittlere Knoten ist der ⌊n / 2⌋-te Knoten unter Verwendung der 0-basierten Indizierung.

So lösen Sie dies effizient.

Die Strategie

Verwenden Sie zwei Zeiger, um die Mitte in einem Durchlauf zu finden.

• Verwenden Sie einen langsamen Zeiger (slow pointer), der sich jeweils einen Schritt vorwärts bewegt.
• Verwenden Sie einen schnellen Zeiger (fast pointer), der sich jeweils zwei Schritte vorwärts bewegt.
• Wenn der schnelle Zeiger das Ende erreicht, befindet sich der langsame Zeiger in der Mitte.
• Verwenden Sie einen dritten Zeiger, um den Knoten vor dem langsamen Zeiger zu verfolgen.

Die Logik

1. Behandeln Sie den Sonderfall. Wenn die Liste nur einen Knoten hat, geben Sie null zurück.
2. Initialisieren Sie die langsamen und schnellen Zeiger am Kopf (head).
3. Bewegen Sie den schnellen Zeiger zwei Schritte und den langsamen Zeiger einen Schritt vorwärts.
4. Aktualisieren Sie einen prev-Zeiger, damit dieser einen Schritt hinter dem langsamen Zeiger bleibt.
5. Sobald die Schleife endet, verbinden Sie den prev-Knoten mit dem Knoten nach dem langsamen Zeiger. Dadurch wird der mittlere Knoten übersprungen.

Komplexität

• Zeitkomplexität: O(n). Sie durchlaufen die Liste einmal.
• Platzkomplexität: O(1). Sie verwenden nur drei Zeiger.

PHP-Implementierung

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

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