Maison > développement back-end > Golang > Parlons du retournement des listes chaînées dans Golang

Parlons du retournement des listes chaînées dans Golang

PHPz
Libérer: 2023-04-23 13:56:30
original
488 Les gens l'ont consulté

Une liste chaînée est une structure de données de base, composée de quelques nœuds. Chaque nœud contient un champ de données et un pointeur vers le nœud suivant. En programmation, il est souvent nécessaire d'opérer sur des listes chaînées, et l'une des opérations les plus élémentaires consiste à retourner la liste chaînée.

Inverser une liste chaînée signifie inverser l'ordre des nœuds dans la liste chaînée. Par exemple, la liste chaînée d'origine est 1->2->3->4, mais après l'avoir retournée, elle devient 4->3->2->1. Dans des applications pratiques, retourner la liste chaînée peut être utilisé pour résoudre certains problèmes, comme imprimer les éléments de la liste chaînée, trouver les nœuds intermédiaires de la liste chaînée, déterminer s'il existe un cycle dans la liste chaînée, etc.

Dans cet article, nous présenterons comment utiliser le langage de programmation Golang pour implémenter le retournement des listes chaînées. Tout d'abord, nous devons définir une structure Node d'un nœud de liste chaînée :

type Node struct {
    Value int
    Next *Node
}
Copier après la connexion

Dans cette structure, Value représente les données stockées dans le nœud de liste chaînée, et Next est un pointeur vers le nœud suivant. Après avoir la structure des nœuds, nous pouvons définir la structure de la liste chaînée :

type List struct {
    Head *Node
}
Copier après la connexion

Dans cette structure, Head est un pointeur vers le nœud principal de la liste chaînée.

Maintenant, jetons un coup d'œil au code sur la façon d'implémenter le retournement de la liste chaînée :

func (l *List) Reverse() {
    if l.Head == nil || l.Head.Next == nil {
        return
    }

    var prev *Node
    current := l.Head
    for current != nil {
        next := current.Next
        current.Next = prev
        prev = current
        current = next
    }
    l.Head = prev
}
Copier après la connexion

Dans ce code, déterminez d'abord si la liste chaînée est vide ou n'a qu'un seul nœud. Si c'est le cas, revenez directement sans retourner. Sinon, définissez deux pointeurs, prev et current, qui pointent respectivement vers le nœud précédent et le nœud actuel de la liste chaînée. Dans la boucle, enregistrez d'abord le nœud à côté du nœud actuel, pointez le nœud actuel vers le nœud précédent, puis déplacez le pointeur vers l'arrière. Enfin, pointez la tête de la liste chaînée vers le dernier nœud précédent après le retournement.

Ensuite, regardons un exemple complet pour mieux comprendre le processus de retournement de liste chaînée :

package main

import "fmt"

type Node struct {
    Value int
    Next *Node
}

type List struct {
    Head *Node
}

func (l *List) Add(value int) {
    node := &Node{Value: value, Next: l.Head}
    l.Head = node
}

func (l *List) Reverse() {
    if l.Head == nil || l.Head.Next == nil {
        return
    }

    var prev *Node
    current := l.Head
    for current != nil {
        next := current.Next
        current.Next = prev
        prev = current
        current = next
    }
    l.Head = prev
}

func (l *List) Print() {
    var node *Node
    for node = l.Head; node != nil; node = node.Next {
        fmt.Print(node.Value, "->")
    }
    fmt.Println()
}

func main() {
    l := &List{}
    l.Add(1)
    l.Add(2)
    l.Add(3)
    l.Add(4)

    fmt.Println("Original List:")
    l.Print()

    l.Reverse()

    fmt.Println("Reversed List:")
    l.Print()
}
Copier après la connexion

Dans cet exemple, nous définissons une liste chaînée l, y ajoutons 4 nœuds, puis retournons et exportons. Les résultats d'exécution sont les suivants :

Original List:
4->3->2->1->
Reversed List:
1->2->3->4->
Copier après la connexion

Comme vous pouvez le voir, le processus de retournement de la liste chaînée est très simple. Il vous suffit de parcourir la liste chaînée et d'inverser les pointeurs un par un.

Dans les applications pratiques, le retournement de liste chaînée est un problème très courant, vous devez donc maîtriser cette compétence. J'espère que cet article pourra aider les lecteurs à mieux comprendre le processus de retournement de liste chaînée et les compétences de programmation associées.

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!

source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal