retournement de la liste chaînée Golang

golang Linked List Flip

En informatique, Linked List est une structure de données de base. Une liste chaînée est composée d'une série de nœuds, chaque nœud contient un élément de données et une référence au nœud suivant. Les listes chaînées sont souvent utilisées pour implémenter des structures de données telles que des piles, des files d'attente et des tables de hachage dans les programmes.

Dans une liste chaînée, chaque nœud a une référence au nœud suivant. Cela rend les listes chaînées idéales pour les opérations d’insertion et de suppression. Mais un inconvénient de la liste chaînée est que lorsque vous accédez à un élément de la liste chaînée, vous devez parcourir l’intégralité de la liste chaînée depuis le début, ce qui rend l’accès à la liste chaînée très compliqué. Pour éviter ce problème, nous devons réorganiser la liste chaînée afin que chaque nœud pointe vers son nœud précédent. De cette façon, nous pouvons accéder à la liste chaînée depuis la fin sans parcourir toute la liste chaînée.

Le retournement de liste chaînée est une opération courante de liste chaînée. Cet article explique comment implémenter le retournement de liste chaînée à l'aide du langage Golang.

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. Chaque nœud contient deux propriétés : Value et Next.

type ListNode struct {
    Value int
    Next  *ListNode
}

Parmi eux, Value est utilisé pour stocker la valeur du nœud actuel, et Next est utilisé pour pointer vers l'adresse du nœud suivant.

2. Implémentation de la fonction de retournement de liste chaînée

Ensuite, nous devons implémenter la fonction de retournement de liste chaînée. La fonction de retournement de liste chaînée doit recevoir le nœud principal d'une liste chaînée en tant que paramètre et renvoyer un nœud principal inversé de la liste chaînée. Le code est le suivant :

func reverseList(head *ListNode) *ListNode {
    // 定义空节点和当前节点
    var prev *ListNode
    curr := head

    // 遍历整个链表
    for curr != nil {
        // 保存当前节点的下一个节点
        next := curr.Next

        // 将当前节点的Next指向前一个节点
        curr.Next = prev

        // 更新prev和curr
        prev = curr
        curr = next
    }

    // 返回翻转后的链表头节点
    return prev
}

Dans cette fonction, nous utilisons trois pointeurs : prev, curr et next. prev pointe vers le nœud qui a été inversé, curr pointe vers le nœud qui doit actuellement être inversé et next pointe vers le nœud suivant de curr.

Nous parcourons toute la liste chaînée, en pointant à chaque fois Next of curr vers prev, et mettons à jour prev et curr. Enfin, renvoyez le nœud principal inversé de la liste chaînée (c'est-à-dire le nœud précédent).

3. Code complet

Ce qui suit est le code Golang complet :

type ListNode struct {
    Value int
    Next  *ListNode
}

func reverseList(head *ListNode) *ListNode {
    // 定义空节点和当前节点
    var prev *ListNode
    curr := head

    // 遍历整个链表
    for curr != nil {
        // 保存当前节点的下一个节点
        next := curr.Next

        // 将当前节点的Next指向前一个节点
        curr.Next = prev

        // 更新prev和curr
        prev = curr
        curr = next
    }

    // 返回翻转后的链表头节点
    return prev
}

Grâce au code ci-dessus, nous avons implémenté avec succès la fonction de retournement de liste chaînée. Dans les applications pratiques, le retournement de liste chaînée est généralement utilisé pour résoudre certains problèmes, tels que l'inversion de chaînes, l'inversion de tableaux, etc. La maîtrise des compétences en matière d'exploitation de listes chaînées est très importante pour écrire des programmes efficaces et stables.

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!