Comment utiliser la récursion PHP pour inverser une liste chaînée

Une liste chaînée est une structure de données très courante, qui est une collection de nœuds. Chaque nœud contient un élément de données et un pointeur vers le nœud suivant. Les listes chaînées peuvent être utilisées pour implémenter des structures de données telles que des piles, des files d'attente et des tables de hachage, et sont souvent rencontrées dans les problèmes d'algorithme.

Dans de nombreux problèmes algorithmiques, la liste chaînée doit être inversée. L'idée de base de l'inversion d'une liste chaînée est de pointer chaque nœud de la liste chaînée vers son nœud précédent, et enfin de faire du premier nœud le nœud de queue de la liste chaînée. Cette opération peut être appliquée dans divers scénarios tels que la recherche, la fusion et le tri de listes chaînées.

Cet article expliquera comment utiliser PHP pour implémenter la fonction d'inversion récursive d'une liste chaînée. Si vous ne connaissez pas grand-chose aux concepts tels que les listes chaînées et la récursivité, vous pouvez d'abord acquérir les connaissances de base pertinentes par vous-même.

Méthode d'implémentation

Dans le processus d'inversion récursive de la liste chaînée, la liste chaînée doit être divisée en deux parties : le premier nœud et la partie restante. Après avoir inversé les parties restantes, insérez le premier nœud à la fin de la liste inversée. Ce processus peut être implémenté en utilisant la récursivité. L'implémentation spécifique est la suivante :

/**
 * 反转链表
 * @param ListNode $head 头节点
 * @return ListNode|null 反转后的头节点
 */
function reverseList($head) {
    // base case
    if ($head == null || $head->next == null) {
        return $head;
    }
    
    // 反转剩余部分
    $newHead = reverseList($head->next);
    
    // 将当前节点插入到反转后的链表末尾
    $head->next->next = $head;
    $head->next = null;
    
    return $newHead;
}

Analyse du code

Dans le code ci-dessus, nous traitons d'abord le cas de base, c'est-à-dire que lorsque le nœud est vide ou que le nœud suivant est vide, le nœud lui-même est renvoyé directement. Ensuite, nous traitons de manière récursive les nœuds restants pour obtenir la liste chaînée inversée.

Ensuite, nous insérons le nœud actuel à la fin de la liste inversée. Plus précisément, nous pointons le nœud suivant du nœud suivant $head->next vers le nœud actuel $head, vidons le nœud suivant de $head et renvoyons enfin le nœud principal inversé $newHead.

De plus, afin de mieux comprendre le code ci-dessus, nous devons également ajouter la définition d'un nœud de liste chaînée :

class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val) {
        $this->val = $val;
    }
}

Cas de test

Afin de vérifier l'exactitude du code ci-dessus, nous pouvons écrire le scénario de test suivant :

$head = new ListNode(1);
$head->next = new ListNode(2);
$head->next->next = new ListNode(3);
$head->next->next->next = new ListNode(4);
$head->next->next->next->next = new ListNode(5);

$newHead = reverseList($head);

print_r($newHead);

En exécutant le scénario de test ci-dessus, nous pouvons obtenir les résultats de sortie suivants :

ListNode Object
(
    [val] => 5
    [next] => ListNode Object
        (
            [val] => 4
            [next] => ListNode Object
                (
                    [val] => 3
                    [next] => ListNode Object
                        (
                            [val] => 2
                            [next] => ListNode Object
                                (
                                    [val] => 1
                                    [next] => 
                                )

                        )

                )

        )

)

Conclusion

Cet article présente comment utiliser la récursivité PHP pour implémenter l'opération d'inversion d'une liste chaînée. Grâce à la démonstration ci-dessus, nous pouvons constater la supériorité des algorithmes récursifs dans la résolution des problèmes de listes chaînées. Dans le développement réel, nous devons choisir l'algorithme le plus approprié pour résoudre le problème en fonction du scénario réel. J'espère que cet article sera utile aux lecteurs !

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!