suchen
HeimBackend-EntwicklungPHP-ProblemSo 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!

Stellungnahme
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
php怎么把负数转为正整数php怎么把负数转为正整数Apr 19, 2022 pm 08:59 PM

php把负数转为正整数的方法:1、使用abs()函数将负数转为正数,使用intval()函数对正数取整,转为正整数,语法“intval(abs($number))”;2、利用“~”位运算符将负数取反加一,语法“~$number + 1”。

php怎么实现几秒后执行一个函数php怎么实现几秒后执行一个函数Apr 24, 2022 pm 01:12 PM

实现方法:1、使用“sleep(延迟秒数)”语句,可延迟执行函数若干秒;2、使用“time_nanosleep(延迟秒数,延迟纳秒数)”语句,可延迟执行函数若干秒和纳秒;3、使用“time_sleep_until(time()+7)”语句。

php字符串有没有下标php字符串有没有下标Apr 24, 2022 am 11:49 AM

php字符串有下标。在PHP中,下标不仅可以应用于数组和对象,还可应用于字符串,利用字符串的下标和中括号“[]”可以访问指定索引位置的字符,并对该字符进行读写,语法“字符串名[下标值]”;字符串的下标值(索引值)只能是整数类型,起始值为0。

php怎么除以100保留两位小数php怎么除以100保留两位小数Apr 22, 2022 pm 06:23 PM

php除以100保留两位小数的方法:1、利用“/”运算符进行除法运算,语法“数值 / 100”;2、使用“number_format(除法结果, 2)”或“sprintf("%.2f",除法结果)”语句进行四舍五入的处理值,并保留两位小数。

php怎么读取字符串后几个字符php怎么读取字符串后几个字符Apr 22, 2022 pm 08:31 PM

在php中,可以使用substr()函数来读取字符串后几个字符,只需要将该函数的第二个参数设置为负值,第三个参数省略即可;语法为“substr(字符串,-n)”,表示读取从字符串结尾处向前数第n个字符开始,直到字符串结尾的全部字符。

php怎么根据年月日判断是一年的第几天php怎么根据年月日判断是一年的第几天Apr 22, 2022 pm 05:02 PM

判断方法:1、使用“strtotime("年-月-日")”语句将给定的年月日转换为时间戳格式;2、用“date("z",时间戳)+1”语句计算指定时间戳是一年的第几天。date()返回的天数是从0开始计算的,因此真实天数需要在此基础上加1。

php怎么替换nbsp空格符php怎么替换nbsp空格符Apr 24, 2022 pm 02:55 PM

方法:1、用“str_replace(" ","其他字符",$str)”语句,可将nbsp符替换为其他字符;2、用“preg_replace("/(\s|\&nbsp\;||\xc2\xa0)/","其他字符",$str)”语句。

php怎么查找字符串是第几位php怎么查找字符串是第几位Apr 22, 2022 pm 06:48 PM

查找方法:1、用strpos(),语法“strpos("字符串值","查找子串")+1”;2、用stripos(),语法“strpos("字符串值","查找子串")+1”。因为字符串是从0开始计数的,因此两个函数获取的位置需要进行加1处理。

See all articles

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

AI Hentai Generator

AI Hentai Generator

Erstellen Sie kostenlos Ai Hentai.

Heiße Werkzeuge

mPDF

mPDF

mPDF ist eine PHP-Bibliothek, die PDF-Dateien aus UTF-8-codiertem HTML generieren kann. Der ursprüngliche Autor, Ian Back, hat mPDF geschrieben, um PDF-Dateien „on the fly“ von seiner Website auszugeben und verschiedene Sprachen zu verarbeiten. Es ist langsamer und erzeugt bei der Verwendung von Unicode-Schriftarten größere Dateien als Originalskripte wie HTML2FPDF, unterstützt aber CSS-Stile usw. und verfügt über viele Verbesserungen. Unterstützt fast alle Sprachen, einschließlich RTL (Arabisch und Hebräisch) und CJK (Chinesisch, Japanisch und Koreanisch). Unterstützt verschachtelte Elemente auf Blockebene (wie P, DIV),

SublimeText3 chinesische Version

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

Dreamweaver Mac

Dreamweaver Mac

Visuelle Webentwicklungstools

EditPlus chinesische Crack-Version

EditPlus chinesische Crack-Version

Geringe Größe, Syntaxhervorhebung, unterstützt keine Code-Eingabeaufforderungsfunktion

Sicherer Prüfungsbrowser

Sicherer Prüfungsbrowser

Safe Exam Browser ist eine sichere Browserumgebung für die sichere Teilnahme an Online-Prüfungen. Diese Software verwandelt jeden Computer in einen sicheren Arbeitsplatz. Es kontrolliert den Zugriff auf alle Dienstprogramme und verhindert, dass Schüler nicht autorisierte Ressourcen nutzen.