Liste chaînée inversée golang

L'inversion de la liste chaînée est un problème classique d'algorithme de structure de données, qui nécessite d'opérer des nœuds sur la liste chaînée, d'inverser la liste chaînée et de renvoyer le nœud principal inversé.

L'utilisation du langage Golang pour implémenter une liste chaînée inversée peut démontrer efficacement les fonctionnalités orientées objet et de fonctionnement du pointeur de Golang. Expliquons en détail comment implémenter une liste chaînée inversée.

1. Définir la structure des nœuds de liste chaînée

Tout d'abord, nous devons définir une structure de nœuds de liste chaînée, qui contient deux variables membres : la valeur et le pointeur vers le nœud suivant.

type ListNode struct {
    Val int
    Next *ListNode
}

2. Inverser la liste chaînée

Ensuite, nous devons écrire une fonction pour inverser la liste chaînée. Cette fonction parcourra la liste chaînée et inversera le pointeur suivant de chaque nœud vers le nœud précédent, et retournera enfin le nœud principal inversé.

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    for head != nil {
        temp := head.Next
        head.Next = prev
        prev = head
        head = temp
    }
    return prev
}

Cette fonction contient un pointeur prev, qui est utilisé pour maintenir le nœud précédent pendant le parcours.

Tout d'abord, nous initialisons le pointeur prev à null, indiquant qu'il se trouve avant le premier nœud de la liste chaînée.

Ensuite, nous commençons à parcourir la liste chaînée.

Dans chaque boucle, nous utilisons un pointeur temporaire supplémentaire pour stocker temporairement le nœud suivant du nœud actuel.

Ensuite, nous inversons le pointeur suivant du nœud actuel vers le pointeur précédent et insérons le nœud actuel dans la position pointée par le pointeur précédent.

Enfin, nous pointons le nœud actuel vers temp afin de pouvoir le parcourir dans la boucle suivante.

3. Testez la liste chaînée inversée

Avec le code ci-dessus, nous avons terminé la mise en œuvre de la liste chaînée inversée. Ensuite, nous pouvons écrire du code de test pour vérifier si notre fonction de liste chaînée inversée est correcte.

func main() {
    head := &ListNode{Val: 1}
    head.Next = &ListNode{Val: 2}
    head.Next.Next = &ListNode{Val: 3}
    head.Next.Next.Next = &ListNode{Val: 4}
    head.Next.Next.Next.Next = &ListNode{Val: 5}
    fmt.Println("Original List: ")
    printList(head)
    reversedList := reverseList(head)
    fmt.Println("Reversed List: ")
    printList(reversedList)
}

func printList(head *ListNode) {
    for head != nil {
        fmt.Printf("%d ", head.Val)
        head = head.Next
    }
    fmt.Println()
}

Dans cette fonction de test, nous créons d'abord une liste chaînée avec 5 nœuds et imprimons l'ordre initial de la liste chaînée. Ensuite, nous appelons la fonction reverseList() pour inverser la liste chaînée et afficher la liste chaînée inversée. A la fin, nous définissons une fonction printList() pour imprimer la liste chaînée.

En exécutant la fonction de test ci-dessus, nous pouvons obtenir les résultats suivants :

Original List: 
1 2 3 4 5 
Reversed List: 
5 4 3 2 1 

Comme le montrent les résultats, nous avons réussi à inverser la liste chaînée.

Résumé

L'inversion d'une liste chaînée est un problème d'algorithme très intéressant et courant, et il est souvent utilisé dans des applications pratiques.

Grâce à cet article, nous avons appris comment implémenter une liste chaînée inversée sur Golang et utilisé les fonctionnalités d'orientation objet et d'opération de pointeur de Golang.

En implémentant nous-mêmes cet algorithme, nous pouvons mieux comprendre la structure des données de la liste chaînée, et en même temps approfondir davantage notre maîtrise du langage golang.

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!