Umgekehrt verknüpfte Liste Golang

Das Umkehren der verknüpften Liste ist ein klassisches Datenstrukturalgorithmusproblem, bei dem Knoten auf der verknüpften Liste bearbeitet, die verknüpfte Liste umgekehrt und der umgekehrte Kopfknoten zurückgegeben werden müssen.

Die Verwendung der Golang-Sprache zum Implementieren einer umgekehrt verknüpften Liste kann die objektorientierten und Zeigeroperationsfunktionen von Golang effektiv demonstrieren. Lassen Sie uns im Detail erklären, wie eine umgekehrt verknüpfte Liste implementiert wird.

1. Definieren Sie die Knotenstruktur der verknüpften Liste.

Zuerst müssen wir eine Knotenstruktur der verknüpften Liste definieren, die zwei Mitgliedsvariablen enthält: Wert und Zeiger auf den nächsten Knoten.

type ListNode struct {
    Val int
    Next *ListNode
}

2. Die verknüpfte Liste umkehren

Als nächstes müssen wir eine Funktion schreiben, um die verknüpfte Liste umzukehren. Diese Funktion durchläuft die verknüpfte Liste, kehrt den nächsten Zeiger jedes Knotens zum vorherigen Knoten um und gibt schließlich den umgekehrten Kopfknoten zurück.

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    for head != nil {
        temp := head.Next
        head.Next = prev
        prev = head
        head = temp
    }
    return prev
}

Diese Funktion enthält einen Zeiger prev, der verwendet wird, um den vorherigen Knoten während des Durchlaufs beizubehalten.

Zuerst initialisieren wir den vorherigen Zeiger auf Null, um anzuzeigen, dass er sich vor dem ersten Knoten der verknüpften Liste befindet.

Dann beginnen wir mit dem Durchlaufen der verknüpften Liste.

In jeder Schleife verwenden wir einen zusätzlichen Zeiger temp, um den nächsten Knoten des aktuellen Knotens vorübergehend zu speichern.

Als nächstes kehren wir den nächsten Zeiger des aktuellen Knotens zum vorherigen Zeiger um und fügen den aktuellen Knoten an der Position ein, auf die der vorherige Zeiger zeigt.

Schließlich verweisen wir den aktuellen Knoten auf temp, damit wir ihn in der nächsten Schleife durchlaufen können.

3. Testen Sie die umgekehrte verknüpfte Liste

Mit dem obigen Code haben wir die Implementierung der umgekehrten verknüpften Liste abgeschlossen. Als Nächstes können wir Testcode schreiben, um zu überprüfen, ob unsere umgekehrt verknüpfte Listenfunktion korrekt ist.

func main() {
    head := &ListNode{Val: 1}
    head.Next = &ListNode{Val: 2}
    head.Next.Next = &ListNode{Val: 3}
    head.Next.Next.Next = &ListNode{Val: 4}
    head.Next.Next.Next.Next = &ListNode{Val: 5}
    fmt.Println("Original List: ")
    printList(head)
    reversedList := reverseList(head)
    fmt.Println("Reversed List: ")
    printList(reversedList)
}

func printList(head *ListNode) {
    for head != nil {
        fmt.Printf("%d ", head.Val)
        head = head.Next
    }
    fmt.Println()
}

In dieser Testfunktion erstellen wir zunächst eine verknüpfte Liste mit 5 Knoten und drucken die ursprüngliche Reihenfolge der verknüpften Liste aus. Anschließend rufen wir die Funktion reverseList() auf, um die verknüpfte Liste umzukehren und die umgekehrte verknüpfte Liste auszugeben. Am Ende definieren wir eine printList()-Funktion zum Drucken der verknüpften Liste.

Wenn wir die obige Testfunktion ausführen, können wir die folgenden Ergebnisse erhalten:

Original List: 
1 2 3 4 5 
Reversed List: 
5 4 3 2 1 

Wie aus den Ergebnissen ersichtlich ist, haben wir die verknüpfte Liste erfolgreich umgekehrt.

Zusammenfassung

Das Umkehren einer verknüpften Liste ist ein sehr interessantes und häufiges Algorithmusproblem und wird häufig in praktischen Anwendungen verwendet.

In diesem Artikel haben wir gelernt, wie man eine umgekehrt verknüpfte Liste auf Golang implementiert und die objektorientierten und Zeigeroperationsfunktionen von Golang verwendet.

Indem wir diesen Algorithmus selbst implementieren, können wir die Datenstruktur der verknüpften Liste besser verstehen und gleichzeitig unsere Beherrschung der Golang-Sprache weiter vertiefen.

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