Comment inverser la liste chaînée dans Golang

L'inversion des listes chaînées est un problème d'algorithme courant, qui nécessite d'inverser l'ordre de la liste chaînée. Pour le langage Golang, l'implémentation de l'inversion de liste chaînée peut être implémentée à l'aide de fonctionnalités de base du langage telles que les pointeurs et les structures Golang.

Ci-dessous, nous présenterons en détail l'implémentation Golang de l'inversion de liste chaînée.

Tout d’abord, jetons un coup d’œil à la structure de base d’une liste chaînée. Une liste chaînée est composée de nœuds et chaque nœud possède un pointeur vers le nœud suivant, c'est-à-dire le pointeur suivant. Le nœud principal de la liste chaînée représente la position de départ de l'ensemble de la liste chaînée, et le pointeur suivant du nœud principal pointe vers le premier nœud. Comme indiqué ci-dessous :

type ListNode struct {
    Val  int
    Next *ListNode
}

Où, Val représente la valeur du nœud et Next représente le pointeur vers le nœud suivant. Il y a deux problèmes auxquels il faut prêter attention lors de la mise en œuvre d'une liste chaînée :

1. Il est nécessaire d'enregistrer le pointeur du nœud principal de la liste chaînée
2. Il est nécessaire d'enregistrer les pointeurs du nœud actuel et du nœud suivant

Après avoir terminé la définition de la liste chaînée, vous pouvez écrire l'implémentation Golang de l'inversion de liste chaînée . La méthode de mise en œuvre spécifique est la suivante :

func reverseList(head *ListNode) *ListNode {
    //边界条件
    if head == nil || head.Next == nil {
        return head
    }
    //定义当前节点和下一个节点指针
    cur, next := head, head.Next
    //头节点指针置为空
    head.Next = nil
    for next != nil {
        //暂存下一个节点的指针
        tmp := next.Next
        //反转节点
        next.Next = cur
        //移动当前节点和下一个节点指针
        cur, next = next, tmp
    }
    return cur
}

Tout d'abord, jugez les conditions aux limites. Si la liste chaînée est vide ou n'a qu'un seul nœud, revenez directement à la liste chaînée d'origine. Définissez ensuite le pointeur de nœud actuel et le pointeur de nœud suivant. Étant donné que l'inversion de liste chaînée nécessite que le nœud actuel pointe vers le nœud précédent, le nœud précédent du premier nœud doit être défini sur zéro. Ensuite, inversez la liste chaînée via une boucle. L'opération d'inversion spécifique est la suivante :

1. Stocker temporairement le pointeur du nœud suivant
2. Inverser le pointeur du nœud actuel pour pointer vers le nœud précédent
3. Déplacer le pointeur du nœud actuel et le nœud suivant. pointer

Enfin, renvoyez le pointeur de nœud de tête de liste inversé.

Dans le processus d'inversion de la liste chaînée à l'aide du code ci-dessus, nous devons appeler cette fonction et transmettre le paramètre de pointeur de tête de liste chaînée. Par exemple :

func main() {
    var head ListNode
    head.Next = &ListNode{Val: 1}
    head.Next.Next = &ListNode{Val: 2}
    head.Next.Next.Next = &ListNode{Val: 3}
    head.Next.Next.Next.Next = &ListNode{Val: 4}
    //链表反转
    head.Next = reverseList(head.Next)
    for head.Next != nil {
        fmt.Println(head.Next.Val)
        head.Next = head.Next.Next 
    }
}

Dans cet exemple de code, nous construisons d'abord une liste chaînée avec 5 nœuds. Appelez ensuite la fonction reverse pour l'inverser. Enfin, en parcourant les nœuds, les nœuds de la liste chaînée inversée sont affichés dans l'ordre.

Grâce aux exemples de code ci-dessus, nous pouvons voir que l'implémentation Golang de l'inversion de liste chaînée est relativement simple et courante. En maîtrisant les opérations de base des listes chaînées et l'utilisation des pointeurs, nous pouvons facilement mettre en œuvre l'opération d'inversion des listes chaîné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!