Golang-Invertierung einfach verknüpfter Listen

Vorwort

In der Informatik ist eine verknüpfte Liste eine grundlegende Datenstruktur, die aus einer Reihe von Knoten besteht, die durch Zeiger miteinander verknüpft sind. Verknüpfte Listen können problemlos Einfüge- und Löschvorgänge implementieren, die Leistung von Zugriffsvorgängen ist jedoch relativ schlecht, da zum Auffinden von Elementen ein Durchlauf erforderlich ist. In diesem Artikel wird erläutert, wie Sie mit Golang den Inversionsalgorithmus einer einfach verknüpften Liste implementieren.

Definition einer einfach verknüpften Liste

In Golang können wir Strukturen verwenden, um einfach verknüpfte Listen zu definieren. Definieren Sie eine Strukturknoten, die den Knoten einer einfach verknüpften Liste darstellt, die den Wert val des Knotens und seinen Zeiger enthält, der auf die Position des nächsten Knotens zeigt.

type Node struct {
    val  int
    next *Node
}

Definieren Sie einen Kopfzeiger, der auf den Kopfknoten der verknüpften Liste zeigt. Wenn die verknüpfte Liste leer ist, zeigt head auf Null.

var head *Node = nil

Initialisierung einer einfach verknüpften Liste

In Golang können wir die neue Funktion verwenden, um den Speicher eines Knotens zuzuweisen und den Zeiger des Knotens zurückzugeben.

func newNode(val int) *Node {
    return &Node{
        val,
        nil,
    }
}

Das Erstellen einer einfach verknüpften Liste kann durch kontinuierliches Hinzufügen von Knoten mithilfe von newNode erreicht werden. Am Beispiel der verknüpften Listen 1, 2 und 3 lautet der Code wie folgt:

node1 := newNode(1)
node2 := newNode(2)
node3 := newNode(3)
  
node1.next = node2
node2.next = node3
head = node1

Inversion einer einfach verknüpften Liste

Es gibt zwei Methoden, um die Umkehrung zu erreichen einer einfach verknüpften Liste: Iteration und Rekursion.

Methode 1: Iteration

Die Kernidee der Iterationsmethode besteht darin, die verknüpfte Liste zu durchlaufen und den Zeiger des aktuellen Knotens auf den vorherigen Knoten zu verweisen, um das zu erreichen Zweck der Umkehrung.

Der spezifische Implementierungsprozess ist wie folgt:

• Definieren Sie drei Zeiger: prev, head, next
• Durchlaufen Sie die verknüpfte Liste und Ändern Sie den nächsten Kopf. Der Zeiger zeigt auf prev
• Zeigen Sie den vorherigen Zeiger auf head
• Zeigen Sie mit head auf next
• Wiederholen Sie die obigen Schritte bis head ist leer
# 🎜🎜#

Der Golang-Implementierungscode lautet wie folgt:

func reverseList1(head *Node) *Node {
    var prev *Node = nil
    var next *Node = nil
  
    for head != nil {
        next = head.next
        head.next = prev
        prev = head
        head = next
    }
  
    return prev
}

Methode 2: Rekursiv

Die Kernidee des Die rekursive Methode besteht darin, zuerst zum Ende der verknüpften Liste zu rekursieren und dann in umgekehrter Reihenfolge die durchlaufenen Knoten zurückzugeben.

Der spezifische Implementierungsprozess ist wie folgt:

Rekursion zum Ende der verknüpften Liste
• Zeigen Sie auf den nächsten Knoten davon Knoten zum vorletzten Knoten#🎜 🎜#
• Zeigen Sie den nächsten vorletzten Knoten auf leer
• Wiederholen Sie die obigen Schritte, bis der Kopfknoten der ursprünglichen verknüpften Liste zurückgegeben wird
# 🎜🎜#
• Golang-Implementierungscode Wie folgt:

func reverseList2(head *Node) *Node {
    if head == nil || head.next == nil {
        return head
    }
  
    newHead := reverseList2(head.next)
    head.next.next = head
    head.next = nil
  
    return newHead
}

Der vollständige Code lautet wie folgt:

package main
  
import (
    "fmt"
)
  
type Node struct {
    val  int
    next *Node
}
  
func newNode(val int) *Node {
    return &Node{
        val,
        nil,
    }
}
  
var head *Node
  
func reverseList1(head *Node) *Node {
    var prev *Node = nil
    var next *Node = nil
  
    for head != nil {
        next = head.next
        head.next = prev
        prev = head
        head = next
    }
  
    return prev
}
  
func reverseList2(head *Node) *Node {
    if head == nil || head.next == nil {
        return head
    }
  
    newHead := reverseList2(head.next)
    head.next.next = head
    head.next = nil
  
    return newHead
}
  
func main() {
    node1 := newNode(1)
    node2 := newNode(2)
    node3 := newNode(3)
  
    node1.next = node2
    node2.next = node3
  
    head = node1
  
    fmt.Println("原链表：")
    for head != nil {
        fmt.Printf("%d->", head.val)
        head = head.next
    }
  
    head = node1
    head = reverseList1(head)
  
    fmt.Println("
迭代法倒转后的链表：")
    for head != nil {
        fmt.Printf("%d->", head.val)
        head = head.next
    }
  
    head = node1
    head = reverseList2(head)
  
    fmt.Println("
递归法倒转后的链表：")
    for head != nil {
        fmt.Printf("%d->", head.val)
        head = head.next
    }
}

Die laufenden Ergebnisse lauten wie folgt:

原链表：
1->2->3->
迭代法倒转后的链表：
3->2->1->
递归法倒转后的链表：
3->2->1->

Fazit

In diesem Artikel wird erläutert, wie Sie mit Golang die Umkehrung einer einfach verknüpften Liste implementieren, und es werden zwei verschiedene Implementierungsmethoden vorgestellt: Iteration und Rekursion. Ich glaube, dass jeder durch das Studium dieses Artikels die Kernideen dieser beiden Methoden beherrscht und sie flexibel auf die tatsächliche Entwicklung anwenden kann.

Das obige ist der detaillierte Inhalt vonGolang-Invertierung einfach verknüpfter Listen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!