Heim > Backend-Entwicklung > Golang > Lassen Sie uns über das Umdrehen verknüpfter Listen in Golang sprechen

Lassen Sie uns über das Umdrehen verknüpfter Listen in Golang sprechen

PHPz
Freigeben: 2023-04-23 13:56:30
Original
488 Leute haben es durchsucht

Eine verknüpfte Liste ist eine grundlegende Datenstruktur, die aus einigen Knoten besteht. Jeder Knoten enthält ein Datenfeld und einen Zeiger auf den nächsten Knoten. Beim Programmieren ist es oft notwendig, mit verknüpften Listen zu arbeiten, und eine der grundlegendsten Operationen besteht darin, die verknüpfte Liste umzudrehen.

Das Umdrehen einer verknüpften Liste bedeutet, dass die Reihenfolge der Knoten in der verknüpften Liste umgekehrt wird. Beispielsweise ist die ursprüngliche verknüpfte Liste 1->2->3->4, aber nach dem Umdrehen wird sie zu 4->3->2->1. In praktischen Anwendungen kann das Umdrehen der verknüpften Liste zur Lösung einiger Probleme verwendet werden, z. B. zum Drucken der Elemente in der verknüpften Liste, zum Suchen der Zwischenknoten der verknüpften Liste, zum Bestimmen, ob die verknüpfte Liste einen Zyklus enthält usw.

In diesem Artikel stellen wir vor, wie man mit der Programmiersprache Golang das Umdrehen verknüpfter Listen implementiert. Zuerst müssen wir einen Strukturknoten eines verknüpften Listenknotens definieren:

type Node struct {
    Value int
    Next *Node
}
Nach dem Login kopieren

In dieser Struktur stellt Value die im verknüpften Listenknoten gespeicherten Daten dar und Next ist ein Zeiger auf den nächsten Knoten. Nachdem wir die Knotenstruktur haben, können wir die Struktur der verknüpften Liste definieren:

type List struct {
    Head *Node
}
Nach dem Login kopieren

In dieser Struktur ist Head ein Zeiger auf den Kopfknoten der verknüpften Liste.

Schauen wir uns nun den Code zur Implementierung des Umdrehens der verknüpften Liste an:

func (l *List) Reverse() {
    if l.Head == nil || l.Head.Next == nil {
        return
    }

    var prev *Node
    current := l.Head
    for current != nil {
        next := current.Next
        current.Next = prev
        prev = current
        current = next
    }
    l.Head = prev
}
Nach dem Login kopieren

Bestimmen Sie in diesem Code zunächst, ob die verknüpfte Liste leer ist oder nur einen Knoten hat. Wenn ja, kehren Sie direkt ohne Umdrehen zurück. Wenn nicht, definieren Sie zwei Zeiger, prev und current, die auf den vorherigen Knoten bzw. den aktuellen Knoten der verknüpften Liste zeigen. Speichern Sie in der Schleife zunächst den Knoten neben dem aktuellen Knoten, zeigen Sie mit dem aktuellen Knoten auf den vorherigen Knoten und bewegen Sie dann den Zeiger nach hinten. Zeigen Sie abschließend mit dem Kopf der verknüpften Liste auf den letzten Knoten prev nach dem Umdrehen.

Als nächstes schauen wir uns ein vollständiges Beispiel an, um den Prozess des Umdrehens verknüpfter Listen besser zu verstehen:

package main

import "fmt"

type Node struct {
    Value int
    Next *Node
}

type List struct {
    Head *Node
}

func (l *List) Add(value int) {
    node := &Node{Value: value, Next: l.Head}
    l.Head = node
}

func (l *List) Reverse() {
    if l.Head == nil || l.Head.Next == nil {
        return
    }

    var prev *Node
    current := l.Head
    for current != nil {
        next := current.Next
        current.Next = prev
        prev = current
        current = next
    }
    l.Head = prev
}

func (l *List) Print() {
    var node *Node
    for node = l.Head; node != nil; node = node.Next {
        fmt.Print(node.Value, "->")
    }
    fmt.Println()
}

func main() {
    l := &List{}
    l.Add(1)
    l.Add(2)
    l.Add(3)
    l.Add(4)

    fmt.Println("Original List:")
    l.Print()

    l.Reverse()

    fmt.Println("Reversed List:")
    l.Print()
}
Nach dem Login kopieren

In diesem Beispiel definieren wir eine verknüpfte Liste l, fügen ihr 4 Knoten hinzu und spiegeln sie dann und exportieren sie. Die laufenden Ergebnisse sind wie folgt:

Original List:
4->3->2->1->
Reversed List:
1->2->3->4->
Nach dem Login kopieren

Wie Sie sehen, ist das Umdrehen der verknüpften Liste sehr einfach. Sie müssen nur die verknüpfte Liste durchlaufen und die Zeiger einzeln umkehren.

In praktischen Anwendungen ist das Umdrehen verknüpfter Listen ein sehr häufiges Problem, daher müssen Sie diese Fähigkeit beherrschen. Ich hoffe, dass dieser Artikel den Lesern helfen kann, den Prozess des Umblätterns verknüpfter Listen und die damit verbundenen Programmierkenntnisse besser zu verstehen.

Das obige ist der detaillierte Inhalt vonLassen Sie uns über das Umdrehen verknüpfter Listen in Golang sprechen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Quelle:php.cn
Erklärung dieser Website
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
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage