Das Beispiel zeigt, wie Golang die Umkehrung verknüpfter Listen implementiert

Die Inversion verknüpfter Listen ist ein klassisches Algorithmusproblem und ein sehr wichtiger Wissenspunkt in Datenstrukturen und Algorithmen. Die Umkehrung verknüpfter Listen kann in der Praxis und in Interviews häufig verwendet werden. Daher ist es für Programmierer sehr wichtig, den Algorithmus zur Umkehrung verknüpfter Listen zu beherrschen.

Es ist auch sehr einfach, den Umkehralgorithmus für verknüpfte Listen in der Sprache Go zu implementieren. Im Folgenden wird gezeigt, wie der Umkehralgorithmus für verknüpfte Listen implementiert wird.

1. Grundlagen verknüpfter Listen

Lassen Sie uns zunächst kurz die Grundkenntnisse verknüpfter Listen vorstellen. Eine verknüpfte Liste ist eine nichtlineare Datenstruktur, die aus mehreren Knoten besteht. Jeder Knoten verfügt über zwei Eigenschaften: eine, die den Wert des Datenelements speichert, und eine andere, die einen Zeiger auf den nächsten Knoten darstellt.

Verknüpfte Listen haben im Vergleich zu Arrays viele Vorteile. Beispielsweise können Elemente dynamisch hinzugefügt oder gelöscht werden, ohne die Anzahl der in der verknüpften Liste gespeicherten Elemente im Voraus zu kennen.

Ein einfacher verknüpfter Listenknoten kann wie folgt definiert werden:

type ListNode struct {
    Val  int
    Next *ListNode
}

In dieser Definition ist Val der in diesem Knoten gespeicherte Wert und Next ist ein Zeiger auf den nächsten Knoten. Wenn dieser Knoten der letzte in der verknüpften Liste ist, zeigt Next auf nil. Val 是这个节点存储的值，Next 是一个指向下一个节点的指针。如果这个节点是链表的最后一个，Next 就指向 nil。

链表的头节点表示链表的开头，通常也称为“哨兵节点”或“虚拟节点”。它不存储任何值，只是指向第一个实际的节点。

2. 链表反转算法

现在我们开始讲解链表反转算法的实现。链表反转算法的基本思路就是遍历整个链表，把每个节点的指针方向反转，最后把头节点指向原链表的尾节点，完成整个链表的反转。

链表反转算法的关键过程就是每个节点的指针反转，具体实现方式如下：

// 将链表反转
func reverseList(head *ListNode) *ListNode {
    var prev, cur *ListNode
    cur = head
    for cur != nil {
        cur.Next, prev, cur = prev, cur, cur.Next
    }
    return prev
}

这个算法的核心就是定义了两个指针 prev 和 cur，分别表示前一个节点和当前节点。从头节点开始遍历整个链表，每次循环交换 prev 和 cur 指针的指向，同时让 cur

Der Kopfknoten der verknüpften Liste stellt den Anfang der verknüpften Liste dar und wird oft auch als „Sentinel-Knoten“ oder „virtueller Knoten“ bezeichnet. Es speichert keinen Wert, sondern zeigt nur auf den ersten tatsächlichen Knoten.

2. Umkehralgorithmus für verknüpfte Listen

Jetzt beginnen wir mit der Erläuterung der Implementierung des Umkehralgorithmus für verknüpfte Listen. Die Grundidee des Umkehralgorithmus für verknüpfte Listen besteht darin, die gesamte verknüpfte Liste zu durchlaufen, die Richtung des Zeigers jedes Knotens umzukehren und schließlich den Kopfknoten auf den Endknoten der ursprünglichen verknüpften Liste zu verweisen, um die Umkehrung abzuschließen gesamte verlinkte Liste.

Der Schlüsselprozess des Umkehralgorithmus für verknüpfte Listen ist die Umkehrung des Zeigers jedes Knotens. Die spezifische Implementierungsmethode ist wie folgt:

func main() {
    // 初始化一个链表
    n1 := &ListNode{Val: 1}
    n2 := &ListNode{Val: 2}
    n3 := &ListNode{Val: 3}
    n4 := &ListNode{Val: 4}
    n1.Next = n2
    n2.Next = n3
    n3.Next = n4
    // 打印原链表
    printList(n1)
    // 反转链表
    newHead := reverseList(n1)
    // 打印反转后的链表
    printList(newHead)
}

// 打印链表
func printList(head *ListNode) {
    p := head
    for p != nil {
        fmt.Printf("%d -> ", p.Val)
        p = p.Next
    }
    fmt.Println("nil")
}

Der Kern dieses Algorithmus besteht darin, zwei Zeiger prev zu definieren und cur, die jeweils den vorherigen Knoten und den aktuellen Knoten darstellen. Durchlaufen Sie die gesamte verknüpfte Liste ausgehend vom Kopfknoten und tauschen Sie dabei jedes Mal die Punkte der Zeiger <code>prev und cur aus, während cur auf den zeigt nächster Knoten.
Testen
🎜Schließlich können wir durch einige Testfälle überprüfen, ob unser Code korrekt ist. 🎜

1 -> 2 -> 3 -> 4 -> nil
4 -> 3 -> 2 -> 1 -> nil

🎜Ausgabe: 🎜rrreee🎜🎜Zusammenfassung🎜🎜🎜Die Umkehrung verknüpfter Listen ist ein sehr klassisches Algorithmusproblem. In diesem Artikel wird erläutert, wie der Umkehralgorithmus verknüpfter Listen in der Go-Sprache implementiert wird. Durch das Erlernen dieses Algorithmus festigen und vertiefen wir unser Verständnis von verknüpften Listen und Zeigern weiter. 🎜

Das obige ist der detaillierte Inhalt vonDas Beispiel zeigt, wie Golang die Umkehrung verknüpfter Listen implementiert. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!