So verwenden Sie die PHP-Rekursion, um eine verknüpfte Liste umzukehren

Eine verknüpfte Liste ist eine sehr häufige Datenstruktur, bei der es sich um eine Sammlung von Knoten handelt. Jeder Knoten enthält ein Datenelement und einen Zeiger auf den nächsten Knoten. Verknüpfte Listen können zur Implementierung von Datenstrukturen wie Stapeln, Warteschlangen und Hash-Tabellen verwendet werden und werden häufig bei Algorithmusproblemen angetroffen.

Bei vielen algorithmischen Problemen muss die verknüpfte Liste umgekehrt werden. Die Grundidee beim Umkehren einer verknüpften Liste besteht darin, jeden Knoten in der verknüpften Liste auf seinen vorherigen Knoten zu verweisen und schließlich den ersten Knoten zum Endknoten der verknüpften Liste zu machen. Dieser Vorgang kann in verschiedenen Szenarien angewendet werden, z. B. beim Suchen, Zusammenführen und Sortieren verknüpfter Listen.

In diesem Artikel wird erläutert, wie Sie mit PHP die Funktion der rekursiven Umkehrung einer verknüpften Liste implementieren. Wenn Sie nicht viel über Konzepte wie verknüpfte Listen und Rekursion wissen, können Sie sich zunächst die entsprechenden Grundkenntnisse selbst aneignen.

Implementierungsmethode

Beim rekursiven Umkehren der verknüpften Liste muss die verknüpfte Liste in zwei Teile aufgeteilt werden: den ersten Knoten und den verbleibenden Teil. Nachdem Sie die restlichen Teile umgekehrt haben, fügen Sie den ersten Knoten am Ende der umgekehrten Liste ein. Dieser Prozess kann mithilfe einer Rekursion implementiert werden. Die spezifische Implementierung lautet wie folgt:

/**
 * 反转链表
 * @param ListNode $head 头节点
 * @return ListNode|null 反转后的头节点
 */
function reverseList($head) {
    // base case
    if ($head == null || $head->next == null) {
        return $head;
    }
    
    // 反转剩余部分
    $newHead = reverseList($head->next);
    
    // 将当前节点插入到反转后的链表末尾
    $head->next->next = $head;
    $head->next = null;
    
    return $newHead;
}

Codeanalyse

Im obigen Code verarbeiten wir zuerst den Basisfall, dh wenn der Knoten leer ist oder der nächste Knoten leer ist, wird der Knoten selbst direkt zurückgegeben. Anschließend verarbeiten wir die verbleibenden Knoten rekursiv, um die umgekehrt verknüpfte Liste zu erhalten.

Als nächstes fügen wir den aktuellen Knoten am Ende der umgekehrten Liste ein. Insbesondere zeigen wir auf den nächsten Knoten des nächsten Knotens $head->neben dem aktuellen Knoten $head, leeren den nächsten Knoten von $head und geben schließlich den umgekehrten Kopfknoten $newHead zurück.

Um den obigen Code besser zu verstehen, müssen wir außerdem die Definition eines verknüpften Listenknotens hinzufügen:

class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val) {
        $this->val = $val;
    }
}

Testfall

Um die Richtigkeit des obigen Codes zu überprüfen, können wir schreiben den folgenden Testfall:

$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);

$newHead = reverseList($head);

print_r($newHead);

Wenn wir den obigen Testfall ausführen, können wir die folgenden Ausgabeergebnisse erhalten:

ListNode Object
(
    [val] => 5
    [next] => ListNode Object
        (
            [val] => 4
            [next] => ListNode Object
                (
                    [val] => 3
                    [next] => ListNode Object
                        (
                            [val] => 2
                            [next] => ListNode Object
                                (
                                    [val] => 1
                                    [next] => 
                                )

                        )

                )

        )

)

Fazit

In diesem Artikel wird erläutert, wie Sie die PHP-Rekursion verwenden, um die Umkehroperation einer verknüpften Liste zu implementieren. Anhand der obigen Demonstration können wir die Überlegenheit rekursiver Algorithmen bei der Lösung verknüpfter Listenprobleme erkennen. In der tatsächlichen Entwicklung müssen wir basierend auf dem tatsächlichen Szenario den am besten geeigneten Algorithmus zur Lösung des Problems auswählen. Ich hoffe, dieser Artikel ist für die Leser hilfreich!

Das obige ist der detaillierte Inhalt vonSo verwenden Sie die PHP-Rekursion, um eine verknüpfte Liste umzukehren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!