Umkehrung der Golang-verknüpften Liste

Golang ist derzeit eine der beliebtesten Programmiersprachen. Seine Einfachheit und Effizienz werden von Entwicklern sehr geschätzt. In Golang werden verknüpfte Listen häufig in verschiedenen Datenstrukturen verwendet. Allerdings ist die Operation verknüpfter Listen relativ komplex, und der Richtigkeit der Zeigeroperation muss besondere Aufmerksamkeit gewidmet werden. In diesem Artikel besprechen wir, wie man eine verknüpfte Liste mit Golang umkehrt.

Was ist eine verknüpfte Liste?

In der Informatik ist eine verknüpfte Liste eine Datenstruktur, die eine Sammlung von Knoten darstellt. Jeder Knoten enthält Daten und einen Zeiger auf den nächsten Knoten. Sein Merkmal besteht darin, dass Knoten effizient eingefügt und gelöscht werden können. Der zufällige Zugriff auf einen Knoten erfordert jedoch das Durchlaufen der gesamten verknüpften Liste.

Die Datenstruktur der verknüpften Liste ist wie folgt:

type Node struct {
    data int
    next *Node
}

wobei data die im Knoten gespeicherten Daten sind und next zeigt auf den nächsten Zeiger auf den Knoten. Wenn next gleich nil ist, bedeutet dies, dass dies der letzte Knoten der verknüpften Liste ist. data是节点存储的数据，next是指向下一个节点的指针。当next等于nil时，表示这是链表的最后一个节点。

链表的遍历和插入操作

遍历链表的基本操作是从链表的头节点开始遍历，直到链表的尾节点。遍历过程中可以对每个节点进行一定的操作，例如输出节点的值。下面是遍历链表的例子：

func printList(head *Node) {
    p := head
    for p != nil {
        fmt.Print(p.data, " ")
        p = p.next
    }
}

对于插入操作，我们需要先找到要插入的位置，然后修改指针的指向。例如，在链表的第三个节点后插入一个新节点，代码如下：

func insert(head *Node, pos int, value int) *Node {
    p := head
    for i := 1; i < pos && p != nil; i++ {
        p = p.next
    }
    if p == nil {
        return head
    }
    newNode := &Node{data: value}
    newNode.next = p.next
    p.next = newNode
    return head
}

链表的反转

反转链表是指将链表中的节点顺序翻转，即原来的第一个节点变为最后一个节点，原来的最后一个节点变为第一个节点。反转链表的过程需要涉及到链表中节点之间指针的反转。下面是反转链表的实现代码：

func reverseList(head *Node) *Node {
    if head == nil || head.next == nil {
        return head
    }
    var prev *Node
    curr := head
    for curr != nil {
        next := curr.next
        curr.next = prev
        prev = curr
        curr = next
    }
    return prev
}

首先，我们判断链表是否为空或者只有一个节点，这种情况下不需要反转，直接返回原来的链表头节点。然后我们定义两个指针，prev指向当前节点的前一个节点，curr指向当前节点。我们从头节点开始遍历链表，每次循环将当前节点的next指针指向其前一个节点，然后将prev和curr

Durchlauf- und Einfügeoperationen verknüpfter Listen

Der grundlegende Vorgang beim Durchlaufen einer verknüpften Liste besteht darin, mit dem Durchlaufen vom Kopfknoten der verknüpften Liste zum Endknoten der verknüpften Liste zu beginnen Liste. Während des Durchquerungsprozesses können an jedem Knoten bestimmte Vorgänge ausgeführt werden, z. B. die Ausgabe des Knotenwerts. Das Folgende ist ein Beispiel für das Durchlaufen einer verknüpften Liste:

func main() {
    head := &Node{data: 1}
    head.next = &Node{data: 2}
    head.next.next = &Node{data: 3}
    head.next.next.next = &Node{data: 4}
    fmt.Println("Original list:")
    printList(head)
    head = reverseList(head)
    fmt.Println("
Reversed list:")
    printList(head)
}

Für den Einfügevorgang müssen wir zuerst die einzufügende Position finden und dann die Zeigerrichtung ändern. Um beispielsweise nach dem dritten Knoten in der verknüpften Liste einen neuen Knoten einzufügen, lautet der Code wie folgt:

Original list:
1 2 3 4
Reversed list:
4 3 2 1

Umkehrung der verknüpften Liste

Umkehrung der verknüpften Liste bezieht sich auf Die Reihenfolge der Knoten in der verknüpften Liste wird umgedreht, dh der ursprüngliche erste Knoten wird zum letzten Knoten und der ursprüngliche letzte Knoten wird zum ersten Knoten. Beim Umkehren einer verknüpften Liste werden die Zeiger zwischen Knoten in der verknüpften Liste umgekehrt. Das Folgende ist der Implementierungscode zum Umkehren der verknüpften Liste: #🎜🎜#rrreee#🎜🎜#Zuerst bestimmen wir, ob die verknüpfte Liste leer ist oder nur einen Knoten hat. In diesem Fall ist keine Umkehrung erforderlich Der ursprüngliche Kopfknoten der verknüpften Liste wird direkt zurückgegeben. Dann definieren wir zwei Zeiger: prev zeigt auf den vorherigen Knoten des aktuellen Knotens und curr zeigt auf den aktuellen Knoten. Wir durchlaufen die verknüpfte Liste ausgehend vom Kopfknoten, und jede Schleife zeigt den next-Zeiger des aktuellen Knotens auf seinen vorherigen Knoten und zeigt dann auf prev und curr zeigt auf Dann wird ein Knoten verschoben, bis die gesamte verknüpfte Liste durchlaufen ist. Schließlich wird der Kopfknoten der umgekehrten Liste zurückgegeben. #🎜🎜##🎜🎜#Der Testcode lautet wie folgt: #🎜🎜#rrreee#🎜🎜#Das Ausgabeergebnis ist: #🎜🎜#rrreee#🎜🎜#Zusammenfassung #🎜🎜##🎜🎜#Dieser Artikel stellt vor Die verknüpfte Liste in Golang Grundlegende Operationen und wie man eine verknüpfte Liste umkehrt. Obwohl die Bedienung verknüpfter Listen etwas kompliziert ist, bietet sie die Vorteile eines effizienten Einfügens und Löschens und wird in verschiedenen Szenarien häufig verwendet. Bei der Verwendung verknüpfter Listen muss besonders auf die Richtigkeit der Zeiger geachtet werden, um Probleme wie Speicherverluste zu vermeiden. #🎜🎜#

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