inversion de liste chaînée unique golang

Avant-propos

En informatique, une liste chaînée est une structure de données de base composée d'une série de nœuds liés les uns aux autres via des pointeurs. Les listes chaînées peuvent facilement implémenter des opérations d'insertion et de suppression, mais les performances des opérations d'accès sont relativement médiocres car un parcours est nécessaire pour trouver des éléments. Cet article expliquera comment utiliser Golang pour implémenter l'algorithme d'inversion d'une liste à chaînage unique.

Définition d'une liste à chaînage unique

Dans Golang, nous pouvons utiliser des structures pour définir des listes à chaînage unique. Définissez une structure Node, qui représente le nœud d'une liste à chaînage unique, qui contient la valeur val du nœud et son pointeur suivant pointant vers la position du nœud suivant.

type Node struct {
    val  int
    next *Node
}

Définissez un pointeur de tête, pointant vers le nœud principal de la liste chaînée. Si la liste chaînée est vide, head pointe vers zéro.

var head *Node = nil

Initialisation d'une liste chaînée unique

Dans Golang, nous pouvons utiliser la nouvelle fonction pour allouer la mémoire d'un nœud et renvoyer le pointeur du nœud.

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

Créez une liste à chaînage unique, qui peut être obtenue en ajoutant continuellement des nœuds à l'aide de newNode. En prenant comme exemple les listes chaînées 1, 2 et 3, le code est le suivant :

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

Inversion d'une liste chaînée unique

Il existe deux méthodes pour réaliser l'inversion d'une liste chaînée unique : l'itération et la récursivité.

Méthode 1 : Itération

L'idée principale de la méthode d'itération est de parcourir la liste chaînée et de pointer le pointeur du nœud actuel vers le nœud précédent pour atteindre l'objectif d'inversion.

Le processus de mise en œuvre spécifique est le suivant :

• Définissez trois pointeurs : prev, head, next
• Parcourez la liste chaînée, pointez le pointeur suivant de head vers prev
• Pointez le pointeur précédent vers head
• Pointez head vers suivant
• Répétez les étapes ci-dessus jusqu'à ce que la tête soit vide

Le code d'implémentation de Golang est le suivant :

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
}

Méthode 2 : Récursion

L'idée principale de la méthode récursive est de récursif jusqu'à la fin du lien lister d'abord, puis renvoyer les nœuds traversés dans l'ordre inverse.

Le processus de mise en œuvre spécifique est le suivant :

• Récurse jusqu'à la fin de la liste chaînée
• Pointez le prochain du nœud vers l'avant-dernier nœud
• Pointez le suivant de l'avant-dernier nœud vers le vide
• Répétez les étapes ci-dessus jusqu'à ce que la liste chaînée d'origine soit renvoyée Le nœud principal

Le code d'implémentation de Golang est le suivant :

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
}

Le code complet est le suivant :

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
    }
}

Les résultats d'exécution sont les suivants :

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

Conclusion

Cet article présente comment pour utiliser Golang pour implémenter l'inversion d'une liste à chaînage unique, et introduit deux méthodes d'implémentation différentes : itération et récursivité. Je pense qu'en étudiant cet article, chacun a maîtrisé les idées fondamentales de ces deux méthodes et peut les appliquer de manière flexible au développement réel.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!