Linked List Cycle

Q: Quelle est la complexité temporelle et spatiale du cycle dans une liste chaînée ?

Les deux approches prennent un temps O(n) , puisque chaque nœud est parcouru un nombre limité de fois. Le marquage des nœuds visités nécessite une mémoire supplémentaire de O(n) . Les pointeurs rapide et lent de Floyd nécessitent O(1) : deux numéros de nœud.

Q: Pourquoi le pointeur rapide ne peut-il pas sauter par-dessus le pointeur lent ?

Dans le cycle, à chaque tour, fast avance de deux nœuds et slow d’un, donc la distance que fast doit encore parcourir pour atteindre slow diminue exactement d’une unité. Une distance qui diminue d’une unité à chaque tour suit la séquence 3, 2, 1, 0 et ne peut pas passer sous zéro ; les deux pointeurs se rejoignent donc sur un nœud.

FacilePointeurs rapide et lent Liste chaînée

+10

Une liste chaînée est stockée dans le tableau next : le nœud i pointe vers le nœud next[i], et -1 signifie que la liste se termine à cet endroit. La tête est le nœud 0. Suis les liens à partir de la tête et renvoie true si tu reviens à un nœud déjà visité, ou false si tu atteins la fin. Les nœuds que le parcours n’atteint jamais ne comptent pas, même s’ils pointent les uns vers les autres en boucle.

Fonction

hasCycle(next: integer-array) → boolean

nextinteger-array: le lien de chaque nœud : next[i] est le nœud après le nœud i, ou -1
Renvoieboolean: vrai si le parcours à partir du nœud 0 revisite un nœud, faux s’il atteint -1

Contraintes

1 ≤ next.length ≤ 10⁴
-1 ≤ next[i] ≤ next.length-1
Plusieurs nœuds peuvent être reliés au même nœud, et certains nœuds peuvent être inaccessibles depuis la tête.

Exemples

Entrée: next = [1, 2, 3, 1]
Sortie: true
Explication: Le parcours passe par 0, 1, 2, 3, puis revient à 1. Le nœud 1 est visité deux fois, donc la liste comporte un cycle passant par les nœuds 1, 2 et 3.

Entrée: next = [2, -1, 1]
Sortie: false
Explication: Le parcours passe par 0, 2, 1 puis atteint -1 : trois nœuds différents, puis la fin ; il n’y a donc pas de cycle.

Entrée: next = [-1, 2, 1]
Sortie: false
Explication: Le nœud 0 pointe vers -1, la liste ne contient donc qu’un seul nœud. Les nœuds 1 et 2 sont liés l’un à l’autre en boucle, mais le parcours depuis la tête ne les atteint jamais.

+16 tests cachés à la soumission

Pour aller plus loin

Peux-tu aussi trouver le nœud où le cycle commence, toujours avec une mémoire supplémentaire de O(1) ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Une liste sans cycle atteint -1 en n liens, mais une liste avec un cycle ne se termine jamais : tu ne peux donc pas attendre la fin. Il te faut un moyen de détecter que le parcours tourne en rond. Mémoriser chaque nœud visité nécessite une mémoire en O(n). Les pointeurs rapide et lent de Floyd permettent de le faire avec deux entiers, car un pointeur qui avance deux fois plus vite doit rattraper le pointeur lent dans une boucle.

Marquez les nœuds que vous visitez

Intuition

Parcourez les nœuds à partir du nœud 0 et marquez chaque nœud lorsque vous le quittez. Si vous arrivez à un nœud déjà marqué, le parcours y est revenu et, à partir de là, il se répète indéfiniment : c’est un cycle. Dans l’exemple 1, vous marquez 0, 1, 2 et 3, et le lien du nœud 3 mène au nœud 1, qui est marqué.

Les nœuds sont numérotés de 0 à n-1, donc un tableau booléen de longueur n sert d’ensemble des nœuds visités. Dans une liste chaînée construite à partir d’objets, vous placeriez plutôt les références des nœuds dans un ensemble de hachage ; l’idée est la même.

Chaque nœud est marqué au plus une fois, et le parcours s’arrête à la première répétition ou à -1, donc il prend au plus n étapes : un temps de O(n) et une mémoire de O(n) pour les marques.

Algorithme

Crée un tableau booléen visited de longueur n, initialisé entièrement à false.
Définis node = 0.
Tant que node n’est pas égal à -1, renvoie true si visited[node] est déjà égal à true.
Sinon, définis visited[node] et passe à next[node].
Lorsque le parcours atteint -1, renvoie false.

def hasCycle(next):
    visited = [False] * len(next)
    node = 0
    while node != -1:
        if visited[node]:
            return True  # back at a node already on the path
        visited[node] = True
        node = next[node]
    return False

Pointeurs rapide et lent (détection de cycle de Floyd)

Intuition

Placez deux pointeurs au début. slow suit un lien par tour et fast en suit deux. Si la liste se termine, fast atteint -1 en premier et vous renvoyez false. S’il y a un cycle, fast y entre en premier et continue de tourner jusqu’à ce que slow arrive aussi.

Une fois que les deux sont dans le cycle, à chaque tour, fast gagne exactement un nœud sur slow. La distance que fast doit encore parcourir pour atteindre slow diminue d’une unité à chaque tour : elle atteint donc zéro et les pointeurs se retrouvent sur le même nœud. En gagnant un nœud à la fois, fast ne peut jamais dépasser slow.

Dans l’exemple 1, après un tour, slow est sur le nœud 1 et fast sur le nœud 2. Après deux tours, slow est sur le nœud 2 et fast est passé par 3, puis 1. Après trois tours, les deux sont sur le nœud 3 : la réponse est donc true.

slow a besoin d’au plus n tours pour entrer dans le cycle et, une fois à l’intérieur, les deux pointeurs se rencontrent avant qu’il termine un tour complet : la complexité temporelle est donc O(n). La seule mémoire utilisée correspond à deux numéros de nœuds.

Algorithme

Définissez slow = 0 et fast = 0.
Tant que fast n’est pas -1 et que next[fast] n’est pas -1, déplacez slow d’un lien et fast de deux liens.
Après chaque déplacement, renvoyez true s’ils se trouvent sur le même nœud.
Lorsque la boucle s’arrête, fast a atteint la fin : renvoyez false.

def hasCycle(next):
    slow = 0
    fast = 0
    # fast needs two links to move; if either is missing, the list ends.
    while fast != -1 and next[fast] != -1:
        slow = next[slow]
        fast = next[next[fast]]
        if slow == fast:
            return True
    return False

Pièges et cas limites

Les bogues ici concernent la fin de la liste et les nœuds à prendre en compte.

Déplacer fast de deux liens sans vérifier les deux. fast et next[fast] doivent tous deux être de vrais nœuds avant de lire next[next[fast]] ; sinon, vous lisez next[-1], ce qui provoque un plantage dans la plupart des langages et renvoie silencieusement le dernier élément en Python.
Comparer les pointeurs avant de les déplacer. Ils commencent tous les deux au nœud 0, donc une vérification au début de la boucle signale un cycle dans chaque liste.
Examiner le tableau entier au lieu du parcours. Dans [-1, 2, 1], les nœuds 1 et 2 forment une boucle, mais la tête se termine immédiatement, donc la réponse est false. Vérifier si une valeur se répète dans next est également incorrect : dans [4, 4, 4, 4, -1], plusieurs nœuds pointent vers le nœud 4 et il n’y a pas de cycle.
Supposer qu’un cycle doit revenir à la tête. Dans [1, 2, 3, 4, 4], le dernier nœud pointe vers lui-même, et dans [0], c’est la tête qui le fait.

Questions fréquentes4

Comment fonctionne la détection de cycle de Floyd ?

Deux pointeurs partent de la tête : l’un avance d’un lien à chaque étape, l’autre de deux. En l’absence de cycle, le pointeur rapide atteint la fin. En présence d’un cycle, les deux finissent par y entrer, le pointeur rapide réduit l’écart d’un nœud à chaque étape, et ils se rejoignent sur le même nœud.

Quelle est la complexité temporelle et spatiale du cycle dans une liste chaînée ?

Les deux approches prennent un temps O(n), puisque chaque nœud est parcouru un nombre limité de fois. Le marquage des nœuds visités nécessite une mémoire supplémentaire de O(n). Les pointeurs rapide et lent de Floyd nécessitent O(1) : deux numéros de nœud.

Pourquoi le pointeur rapide ne peut-il pas sauter par-dessus le pointeur lent ?

Dans le cycle, à chaque tour, fast avance de deux nœuds et slow d’un, donc la distance que fast doit encore parcourir pour atteindre slow diminue exactement d’une unité. Une distance qui diminue d’une unité à chaque tour suit la séquence 3, 2, 1, 0 et ne peut pas passer sous zéro ; les deux pointeurs se rejoignent donc sur un nœud.

Peux-tu détecter le cycle en comptant les étapes ?

Dans cette représentation en tableau, oui : une liste sans cycle atteint -1 en moins de n liens. Ainsi, parcourir n liens sans atteindre la fin prouve qu’il y a un cycle, avec une mémoire en O(1). Cette méthode nécessite de connaître le nombre de nœuds, information qu’une liste constituée de pointeurs ne fournit pas, et les compter au préalable ne se termine jamais en présence d’un cycle. La méthode de Floyd ne nécessite aucun comptage.

Python

def hasCycle(next):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

next = [1, 2, 3, 1]

Attendu

true