Liste chaînée inversée sur une ligne

L'éditeur php Yuzai vous présente un algorithme de structure de données commun - "Liste chaînée inversée intra-ligne". Dans cet algorithme, nous devons inverser l'ordre des nœuds dans une liste chaînée. Grâce à une implémentation de code concise et efficace, nous pouvons effectuer cette opération en une seule ligne, en inversant complètement l'ordre de la liste chaînée. Cet algorithme est très utile dans la programmation réelle et peut jouer un rôle important à la fois dans le traitement des données et dans la conception d'algorithmes. Découvrons ensemble ce merveilleux algorithme !

Contenu de la question

Je viens de trouver la solution pour la liste chaînée inversée en utilisant une ligne en go sur leetcode. Cela fonctionne, mais je ne comprends pas comment le mettre en œuvre.

Ça y est :

func reverselist(head *listnode) (prev *listnode) {
    for head != nil {
        prev, head, head.next = head, head.next, prev 
    }
    
    return
}

Par exemple, que la liste soit [1->2->3->4->5->nil].

Je sais que ça marche comme ça :

1. Exécuter en premier head.next = prev (head.next = nil, 所以现在 head = [1->nil])

2. Alors, prev = head （在这一步 prev = [1->nil] 就像上一步中的 headidem)

3. head = head.next 这就是魔法。对于第二步go中的prev，使用head = [1->nil]，但是在这一步之后head = [2->3->4->5->nil]

Alors quand head != nil 时，它会进行迭代，并在第二步 prev = [2->1->nil] 、 head = [3->4->5->nil] et ainsi de suite.

Cette ligne peut être exprimée comme suit :

for head != nil {
        a := *head
        prev, a.Next = &a, prev
        head = head.Next
    }

Ai-je raison ? Pourquoi cela arrive-t-il?

Solution

La variable sur le côté gauche de l'expression sera affectée à la valeur sur le côté droit de l'expression à ce moment-là. C’est une utilisation intelligente du langage.

Pour faciliter la compréhension, regardons un exemple.

Paramètres

Voici notre liste de liens : 1 -> 2 -> 3 -> 4 ->

Avant l'exécution de la fonction,

La tête est le *nœud 1
prev est zéro (non initialisé)
head.next est *nœud 2

Pas à pas

prev, head, head.next = head, head.next, prev

Décomposons-le,

prev (nil) = head (*nœud 1)
head (*Nœud 1) = head.next (*Nœud 2)
head.next (*nœud 2) = précédent (nil)

Prochaine itération,

prev (*nœud 1) = tête (*nœud 2)
head (*nœud 2) = head.next (*nœud 3)
head.next (*nœud 3) = prev (*nœud 1)

Résumé

Fondamentalement, il inverse

au nœud précédent et se déplace vers le nœud précédent et se dirige vers le nœud suivant. head.next

Comparez cela à un algorithme de manuel pour que ce soit clair :

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode

    for head != nil {
        nextTemp := head.Next
        head.Next = prev
        prev = head
        head = nextTemp
    }

    return prev
}

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!