Comment détecter les listes chaînées de cycle en PHP et Go

Le problème du nœud d'entrée de l'anneau dans la liste chaînée est une question super classique, que ce soit en entretien ou en cours d'examen d'entrée de troisième cycle. La solution généralement admise est la solution des doubles pointeurs (pointeurs rapides et lents). Bien sûr, on en parle depuis longtemps. Aujourd'hui, nous allons le présenter.

Étant donné une liste chaînée, s'il s'agit d'une liste chaînée cyclique, implémentez un algorithme pour renvoyer le nœud de départ du cycle. La définition d'une liste chaînée en anneau : Si l'élément suivant d'un nœud dans la liste chaînée pointe vers le nœud qui est apparu avant lui, cela indique qu'il y a un cycle dans la liste chaînée.

Idée de résolution de problèmes 1

Parcourez la liste chaînée et placez chaque résultat dans la carte S'il y a des éléments répétés, il y a une liste chaînée circulaire

/** 
* Definition for singly-linked list. 
* type ListNode struct { 
* Val int * Next *ListNode 
* } 
*/
func detectCycle(head *ListNode) *ListNode {
    visited := make(map[*ListNode]struct{}, 1)
    work := head

    for work != nil {
        _, ok := visited[work]
        if ok {
            return work
        } else {
            visited[work] = struct{}{}
        }
        work = work.Next
    }

    return nil}

Idée de résolution de problèmes 2

Solution de pointeur rapide et lent : Nous définir deux Les mains sont rapides et pleines. Le pointeur lent se déplace d'un pas à la fois, tandis que le pointeur rapide se déplace de deux pas à la fois. Initialement, le pointeur lent est en position head et le pointeur rapide est en position head.next. De cette façon, si le pointeur rapide rattrape le pointeur lent pendant le mouvement, cela signifie que la liste chaînée est une liste chaînée circulaire. Sinon, le pointeur rapide atteindra la fin de la liste chaînée et la liste chaînée n’est pas une liste chaînée circulaire.

/** 
* Definition for a singly-linked list. 
* class ListNode { 
* public $val = 0; 
* public $next = null; 
* function __construct($val) { $this->val = $val; } 
* } 
*/class Solution {
    /** 
    * @param ListNode $head * @return Boolean 
    */
    function hasCycle($head) {
        $fast = $head;
        $slow = $head;

        while ($fast != null && $fast->next != null) {
            $fast = $fast->next->next;
            $slow = $slow->next;
            if ($fast === $slow) {
                return true;
            }
        }
        return false;
    }}

Recommandé : "Résumé des questions d'entretien PHP 2021 (collection)" "Tutoriel vidéo PHP"

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!