So kehren Sie verknüpfte Listen in Golang um

Die Umkehrung verknüpfter Listen ist ein häufiges Algorithmusproblem, das eine Umkehrung der Reihenfolge der verknüpften Listen erfordert. Für die Golang-Sprache kann die Implementierung der Inversion verknüpfter Listen mithilfe grundlegender Sprachfunktionen wie Golang-Zeiger und -Strukturen implementiert werden.

Im Folgenden stellen wir die Golang-Implementierung der verknüpften Listeninversion im Detail vor.

Werfen wir zunächst einen Blick auf die Grundstruktur einer verknüpften Liste. Eine verknüpfte Liste besteht aus Knoten, und jeder Knoten hat einen Zeiger auf den nächsten Knoten, also den nächsten Zeiger. Der Kopfknoten der verknüpften Liste stellt die Startposition der gesamten verknüpften Liste dar, und der nächste Zeiger des Kopfknotens zeigt auf den ersten Knoten. Wie unten gezeigt:

type ListNode struct {
    Val  int
    Next *ListNode
}

Wobei Val den Wert des Knotens darstellt und Next den Zeiger auf den nächsten Knoten darstellt. Bei der Implementierung einer verknüpften Liste müssen zwei Probleme beachtet werden:

1. Es ist notwendig, den Zeiger des Kopfknotens der verknüpften Liste aufzuzeichnen.
2. Es ist notwendig, die Zeiger des aktuellen Knotens und des aktuellen Knotens aufzuzeichnen Nächster Knoten

Nachdem Sie die Definition der verknüpften Liste abgeschlossen haben, können Sie die Golang-Implementierung der Inversion verknüpfter Listen schreiben. Die spezifische Implementierungsmethode lautet wie folgt:

func reverseList(head *ListNode) *ListNode {
    //边界条件
    if head == nil || head.Next == nil {
        return head
    }
    //定义当前节点和下一个节点指针
    cur, next := head, head.Next
    //头节点指针置为空
    head.Next = nil
    for next != nil {
        //暂存下一个节点的指针
        tmp := next.Next
        //反转节点
        next.Next = cur
        //移动当前节点和下一个节点指针
        cur, next = next, tmp
    }
    return cur
}

Beurteilen Sie zunächst die Randbedingungen. Wenn die verknüpfte Liste leer ist oder nur einen Knoten hat, kehren Sie direkt zur ursprünglichen verknüpften Liste zurück. Definieren Sie dann den aktuellen Knotenzeiger und den nächsten Knotenzeiger. Da die Umkehrung der verknüpften Liste erfordert, dass der aktuelle Knoten auf den vorherigen Knoten zeigt, muss der vorherige Knoten des ersten Knotens auf Null gesetzt werden. Kehren Sie dann die verknüpfte Liste durch eine Schleife um. Die spezifische Umkehroperation lautet:

1. Speichern Sie vorübergehend den Zeiger des nächsten Knotens.
2. Invertieren Sie den aktuellen Knotenzeiger, um auf den vorherigen Knoten zu zeigen Zeiger
Zum Schluss wird der umgekehrte Listenkopfknotenzeiger zurückgegeben.

Beim Umkehren der verknüpften Liste mit dem obigen Code müssen wir diese Funktion aufrufen und den Kopfzeigerparameter der verknüpften Liste übergeben. Zum Beispiel:

func main() {
    var head ListNode
    head.Next = &ListNode{Val: 1}
    head.Next.Next = &ListNode{Val: 2}
    head.Next.Next.Next = &ListNode{Val: 3}
    head.Next.Next.Next.Next = &ListNode{Val: 4}
    //链表反转
    head.Next = reverseList(head.Next)
    for head.Next != nil {
        fmt.Println(head.Next.Val)
        head.Next = head.Next.Next 
    }
}

In diesem Beispielcode erstellen wir zunächst eine verknüpfte Liste mit 5 Knoten. Rufen Sie dann die Umkehrfunktion auf, um es umzukehren. Schließlich werden durch Durchlaufen der Knoten die umgekehrten verknüpften Listenknoten der Reihe nach ausgegeben.

Anhand der obigen Codebeispiele können wir sehen, dass die Golang-Implementierung der Inversion verknüpfter Listen relativ einfach und üblich ist. Durch die Beherrschung der Grundoperationen verknüpfter Listen und der Verwendung von Zeigern können wir die Umkehroperation verknüpfter Listen problemlos implementieren.

Das obige ist der detaillierte Inhalt vonSo kehren Sie verknüpfte Listen in Golang um. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!