L'exemple montre comment Golang implémente l'inversion des listes chaînées

L'inversion de liste chaînée est un problème d'algorithme classique et un point de connaissance très important dans les structures de données et les algorithmes. L'inversion de liste chaînée peut être largement utilisée dans la pratique et les entretiens, il est donc très nécessaire que les programmeurs maîtrisent l'algorithme d'inversion de liste chaînée.

Il est également très simple d'implémenter l'algorithme d'inversion de liste chaînée en langage Go. Ci-dessous, nous montrerons comment implémenter l'algorithme d'inversion de liste chaînée.

1. Bases des listes chaînées

Tout d'abord, présentons brièvement les connaissances de base des listes chaînées. Une liste chaînée est une structure de données non linéaire composée de plusieurs nœuds. Chaque nœud possède deux propriétés : une qui stocke la valeur de l'élément de données et une autre qui est un pointeur vers le nœud suivant.

Les listes chaînées présentent de nombreux avantages par rapport aux tableaux. Par exemple, des éléments peuvent être ajoutés ou supprimés dynamiquement sans connaître à l'avance le nombre d'éléments stockés dans la liste chaînée.

Un simple nœud de liste chaînée peut être défini comme :

type ListNode struct {
    Val  int
    Next *ListNode
}

Dans cette définition, Val est la valeur stockée dans ce nœud, et Next est un pointeur vers le suivant nœud . Si ce nœud est le dernier de la liste chaînée, Suivant pointe vers nil. Val 是这个节点存储的值，Next 是一个指向下一个节点的指针。如果这个节点是链表的最后一个，Next 就指向 nil。

链表的头节点表示链表的开头，通常也称为“哨兵节点”或“虚拟节点”。它不存储任何值，只是指向第一个实际的节点。

2. 链表反转算法

现在我们开始讲解链表反转算法的实现。链表反转算法的基本思路就是遍历整个链表，把每个节点的指针方向反转，最后把头节点指向原链表的尾节点，完成整个链表的反转。

链表反转算法的关键过程就是每个节点的指针反转，具体实现方式如下：

// 将链表反转
func reverseList(head *ListNode) *ListNode {
    var prev, cur *ListNode
    cur = head
    for cur != nil {
        cur.Next, prev, cur = prev, cur, cur.Next
    }
    return prev
}

这个算法的核心就是定义了两个指针 prev 和 cur，分别表示前一个节点和当前节点。从头节点开始遍历整个链表，每次循环交换 prev 和 cur 指针的指向，同时让 cur

Le nœud principal de la liste chaînée représente le début de la liste chaînée, souvent aussi appelé « nœud sentinelle » ou « nœud virtuel ». Il ne stocke aucune valeur, pointe simplement vers le premier nœud réel.

2. Algorithme d'inversion de liste chaînée

Maintenant, nous commençons à expliquer la mise en œuvre de l'algorithme d'inversion de liste chaînée. L'idée de base de l'algorithme d'inversion de liste chaînée est de parcourir toute la liste chaînée, d'inverser la direction du pointeur de chaque nœud et enfin de pointer le nœud de tête vers le nœud de queue de la liste chaînée d'origine pour terminer l'inversion du liste chaînée entière.

Le processus clé de l'algorithme d'inversion de liste chaînée est l'inversion du pointeur de chaque nœud. La méthode de mise en œuvre spécifique est la suivante :

func main() {
    // 初始化一个链表
    n1 := &ListNode{Val: 1}
    n2 := &ListNode{Val: 2}
    n3 := &ListNode{Val: 3}
    n4 := &ListNode{Val: 4}
    n1.Next = n2
    n2.Next = n3
    n3.Next = n4
    // 打印原链表
    printList(n1)
    // 反转链表
    newHead := reverseList(n1)
    // 打印反转后的链表
    printList(newHead)
}

// 打印链表
func printList(head *ListNode) {
    p := head
    for p != nil {
        fmt.Printf("%d -> ", p.Val)
        p = p.Next
    }
    fmt.Println("nil")
}

Le cœur de cet algorithme est de définir deux pointeurs prev. et cur, représentant respectivement le nœud précédent et le nœud actuel. Parcourez toute la liste chaînée en commençant par le nœud principal, en échangeant à chaque fois les points des pointeurs <code>prev et cur, tout en laissant cur pointer vers le nœud suivant.
Tests
🎜Enfin, nous pouvons vérifier que notre code est correct grâce à quelques cas de test. 🎜

1 -> 2 -> 3 -> 4 -> nil
4 -> 3 -> 2 -> 1 -> nil

🎜Sortie : 🎜rrreee🎜🎜Résumé🎜🎜🎜L'inversion de liste chaînée est un problème d'algorithme très classique. Cet article présente comment implémenter l'algorithme d'inversion de liste chaînée en langage Go. En apprenant cet algorithme, nous consolidons et approfondissons davantage notre compréhension des listes chaînées et des pointeurs. 🎜

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!