C'est une question préférée à poser aux nouveaux développeurs. Assez simple si vous avez eu un cours décent sur les structures de données.
Inversez une seule liste chaînée. (Voici le Leetcode 206)
Pour l'implémentation, j'ai choisi de faire de la liste chaînée un type générique.
type Node[T any] struct { Data T Next *Node[T] } type LinkedList[T any] struct { Head *Node[T] } func (ll *LinkedList[T]) Append(data T) { newNode := &Node[T]{Data: data, Next: nil} if ll.Head == nil { ll.Head = newNode return } current := ll.Head for current.Next != nil { current = current.Next } current.Next = newNode }
Et pour la fonction inverse, cela se fait en un seul passage en reconnaissant que tout ce que nous avons à faire est de maintenir un pointeur vers le nœud précédent, puis de définir le « suivant » d'un nœud donné sur le précédent.
Lorsque nous atteignons la fin, nous savons que le nœud actuel est la nouvelle « tête » de la liste.
func (ll *LinkedList[T]) ReverseLinkedList() { var prev *Node[T] = nil var ptr *Node[T] = ll.Head for ptr != nil { var next *Node[T] = ptr.Next ptr.Next = prev prev = ptr if next == nil { ll.Head = ptr } ptr = next } }
Avons-nous manqué une condition aux limites ? Quelles complications s’ajoutent si la liste est désormais une liste doublement chaînée ? Faites-le-moi savoir dans les commentaires.
Merci !
Le code de cet article et de tous les articles de cette série peut être trouvé ici
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!