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 }
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 }
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 }
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() }
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->
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!