Umgekehrte verknüpfte Liste in einer Zeile

php-Editor Yuzai stellt Ihnen einen gängigen Datenstrukturalgorithmus vor – „Intra-row Reverse Linked List“. In diesem Algorithmus müssen wir die Reihenfolge der Knoten in einer verknüpften Liste umkehren. Durch eine präzise und effiziente Codeimplementierung können wir diesen Vorgang in einer Zeile abschließen und dabei die Reihenfolge der verknüpften Liste vollständig umkehren. Dieser Algorithmus ist in der tatsächlichen Programmierung sehr nützlich und kann sowohl bei der Datenverarbeitung als auch beim Algorithmusdesign eine wichtige Rolle spielen. Lassen Sie uns gemeinsam etwas über diesen wunderbaren Algorithmus lernen!

Frageninhalt

Ich habe gerade die Lösung für eine umgekehrt verknüpfte Liste mit einer Zeile in go on leetcode gefunden. Es funktioniert, aber ich verstehe nicht wie.

Das ist es:

func reverselist(head *listnode) (prev *listnode) {
    for head != nil {
        prev, head, head.next = head, head.next, prev 
    }
    
    return
}

Lassen Sie zum Beispiel die Liste sein [1->2->3->4->5->nil].

Ich weiß, dass es so funktioniert:

1. Zuerst ausführen head.next = prev (head.next = nil, 所以现在 head = [1->nil])

2. Dann prev = head （在这一步 prev = [1->nil] 就像上一步中的 headdasselbe)

3. head = head.next 这就是魔法。对于第二步go中的prev，使用head = [1->nil]，但是在这一步之后head = [2->3->4->5->nil]

Also wann head != nil 时，它会进行迭代，并在第二步 prev = [2->1->nil] 、 head = [3->4->5->nil] und so weiter.

Diese Zeile kann ausgedrückt werden als:

for head != nil {
        a := *head
        prev, a.Next = &a, prev
        head = head.Next
    }

Habe ich recht? Warum passiert das?

Lösung

Die Variable auf der linken Seite des Ausdrucks wird zu diesem Zeitpunkt dem Wert auf der rechten Seite des Ausdrucks zugewiesen. Das ist ein geschickter Sprachgebrauch.

Um es einfacher zu verstehen, schauen wir uns ein Beispiel an.

Einstellungen

Hier ist unsere Linkliste: 1 -> 3 ->

Bevor die Funktion ausgeführt wird,

Der Kopf ist *Knoten 1
prev ist Null (nicht initialisiert)
head.next ist *Knoten 2

Schritt für Schritt

prev, head, head.next = head, head.next, prev

Lassen Sie es uns aufschlüsseln,

prev (nil) = head (*Knoten 1)
head (*Node 1) = head.next (*Node 2)
head.next (*Knoten 2) = prev (nil)

Nächste Iteration,

prev (*Knoten 1) = Kopf (*Knoten 2)
head (*Knoten 2) = head.next (*Knoten 3)
head.next (*Knoten 3) = prev (*Knoten 1)

Zusammenfassung

Im Grunde kehrt es

zum vorherigen Knoten zurück und bewegt sich zurück und geht zum nächsten Knoten. head.next

Vergleichen Sie dies mit einem Lehrbuchalgorithmus in Go, um es klar zu machen:

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode

    for head != nil {
        nextTemp := head.Next
        head.Next = prev
        prev = head
        head = nextTemp
    }

    return prev
}

Das obige ist der detaillierte Inhalt vonUmgekehrte verknüpfte Liste in einer Zeile. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!