Knoten aus der im Array vorhandenen verknüpften Liste löschen

3217. Knoten aus der im Array vorhandenen verknüpften Liste löschen

Schwierigkeit:Mittel

Themen: Array, Hash-Tabelle, verknüpfte Liste

Sie erhalten ein Array von Ganzzahlen und den Kopf einer verknüpften Liste. Gibt den Kopf der geänderten verknüpften Liste zurück, nachdem alle Knoten aus der verknüpften Liste entfernt wurden, deren Wert in Nums vorhanden ist.

Beispiel 1:

• Eingabe: nums = [1,2,3], head = [1,2,3,4,5]
• Ausgabe: [4,5]
• Erklärung: Entfernen Sie die Knoten mit den Werten 1, 2 und 3.

Beispiel 2:

• Eingabe:Eingabe: nums = [1], head = [1,2,1,2,1,2]
• Ausgabe: [2,2,2]
• Erklärung: Entfernen Sie die Knoten mit dem Wert 1.

Beispiel 3:

• Eingabe: nums = [5], head = [1,2,3,4]
• Ausgabe: [1,2,3,4] Kein Knoten hat den Wert 5.

Einschränkungen:

• 1 5
• 1 5
• Alle Elemente in Nums sind eindeutig.
• Die Anzahl der Knoten in der angegebenen Liste liegt im Bereich [1, 10⁵].
• 1 5
• Die Eingabe wird so generiert, dass es mindestens einen Knoten in der verknüpften Liste gibt, der einen Wert hat, der in Nums nicht vorhanden ist.

Hinweis:

1. Fügen Sie alle Elemente von Nums zu einem Set hinzu.
2. Scannen Sie die Liste, um zu prüfen, ob das aktuelle Element gelöscht werden soll, indem Sie „Set“ markieren.

Lösung:

Wir müssen die verknüpfte Liste durchlaufen und alle Knoten entfernen, die einen Wert im Array nums haben.

Ansatz:

1. Hash-Set für schnelle Suche: Da die Prüfung, ob ein Wert in Zahlen vorhanden ist, effizient sein muss, werden wir Zahlen in ein Hash-Set umwandeln. Dies ermöglicht die O(1)-Suche für jeden Wert.
2. Durch die verknüpfte Liste iterieren: Wir durchlaufen die verknüpfte Liste und entfernen Knoten, deren Werte im Hash-Set vorhanden sind.
3. Zeigermanipulation: Während der Iteration passen wir die Zeiger an, um Knoten zu „überspringen“, die mit Werten im Nums-Array übereinstimmen.

Schritte:

1. Konvertieren Sie Zahlen in einen Hash-Satz für die O(1)-Suche.
2. Durchlaufen Sie die verknüpfte Liste mit zwei Zeigern: einem für den aktuellen Knoten und einem für den vorherigen Knoten, um Knoten effizient zu entfernen.
3. Überprüfen Sie für jeden Knoten, ob der Wert im Hash-Set enthalten ist. Wenn dies der Fall ist, aktualisieren Sie den nächsten Knoten des vorherigen Knotens, um den aktuellen Knoten zu überspringen.

Lassen Sie uns diese Lösung in PHP implementieren: 3217. Knoten aus der im Array vorhandenen verknüpften Liste löschen

<?php // Definition for a singly-linked list node.
class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

class Solution {

    /**
     * @param Integer[] $nums
     * @param ListNode $head
     * @return ListNode
     */
    function removeElements($head, $nums) {
        ...
        ...
        ...
        /**
         * go to ./solution.php
         */
    }
}

// Example usage:

// Linked List: 1 -> 2 -> 3 -> 4 -> 5
$head = new ListNode(1);
$head->next = new ListNode(2);
$head->next->next = new ListNode(3);
$head->next->next->next = new ListNode(4);
$head->next->next->next->next = new ListNode(5);

// Array nums: [1, 2, 3]
$nums = [1, 2, 3];

$solution = new Solution();
$result = $solution->removeElements($head, $nums);

// Function to print the linked list
function printList($node) {
    while ($node !== null) {
        echo $node->val . " ";
        $node = $node->next;
    }
}

// Print the resulting linked list
printList($result); // Output: 4 5
?>

Erläuterung:

1. removeElements($head, $nums):

   • Wir konvertieren Zahlen zunächst in einen Hash-Satz ($numSet = array_flip($nums);) für schnelle Suchvorgänge.
   • Ein Dummy-Knoten wird erstellt und mit dem Kopf der Liste verknüpft. Dies trägt dazu bei, Randfälle wie das Entfernen des Kopfknotens zu vereinfachen.
   • Der vorherige Zeiger verfolgt den Knoten vor dem aktuellen, sodass wir den aktuellen Knoten entfernen können, indem wir ihn in der Liste überspringen.
   • Für jeden Knoten prüfen wir, ob sein Wert in numSet enthalten ist. Wenn dies der Fall ist, entfernen wir ihn, indem wir den Zeiger prev->next anpassen, um den aktuellen Knoten zu überspringen.

2. Edge Cases:

   • Wenn der Kopfknoten entfernt werden muss, stellt der Dummy-Knoten sicher, dass der Kopf sauber entfernt werden kann und trotzdem die richtige Liste zurückgegeben wird.
   • Behandelt Fälle, in denen mehrere aufeinanderfolgende Knoten entfernt werden müssen.

3. Komplexität:

   • Zeitkomplexität: O(n), wobei n die Anzahl der Knoten in der verknüpften Liste ist. Wir besuchen jeden Knoten einmal. Um Zahlen in eine Menge umzuwandeln, werden O(m) benötigt, wobei m die Größe von Zahlen ist.
   • Raumkomplexität: O(m) zum Speichern des Zahlensatzes.

Beispielhafte Vorgehensweise:

Für die Eingabe nums = [1, 2, 3] und head = [1, 2, 3, 4, 5] wird der Algorithmus:

• Beginnen Sie bei Knoten 1, prüfen Sie, ob 1 in Zahlen enthalten ist, und entfernen Sie es.
• Gehen Sie zu Knoten 2, prüfen Sie, ob 2 in Nums enthalten ist, und entfernen Sie ihn.
• Gehen Sie zu Knoten 3, prüfen Sie, ob 3 in Nums enthalten ist, und entfernen Sie ihn.
• Gehen Sie zu Knoten 4 und 5, die nicht in Nummern enthalten sind, damit sie in der Liste bleiben.

Die resultierende verknüpfte Liste ist [4, 5].

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt vonKnoten aus der im Array vorhandenen verknüpften Liste löschen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!