0Pricing
DSA Interview Prep · Leçon

Détection de cycles avec l’algorithme de Floyd

Détectez les cycles avec l’approche des pointeurs lent et rapide, trouvez le point d’entrée du cycle et démontrez mathématiquement la correction de l’algorithme.

Détection de cycles avec l’algorithme de Floyd est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.

Qu'est-ce qu'un cycle dans une liste chaînée ?

Un cycle dans une liste chaînée se produit lorsqu'un pointeur next d'un nœud pointe vers un nœud déjà parcouru, créant une boucle infinie. Parcourir une telle liste avec une boucle while head ne se terminerait jamais. La détection de cycles est un problème classique d'entretien et constitue la base d'algorithmes de pointeurs plus avancés.

L'approche naïve stocke chaque nœud parcouru dans un ensemble et vérifie son appartenance à cet ensemble — O(n) de temps et O(n) d'espace. L'algorithme de Floyd résout le même problème en O(n) de temps et avec un espace O(1), ce qui est attendu lors des entretiens.

Algorithme des pointeurs lent et rapide de Floyd

La détection de cycles de Floyd (la « tortue et le lièvre ») utilise deux pointeurs : slow avance d'une étape à la fois, tandis que fast avance de deux étapes. S'il n'existe aucun cycle, fast atteint la valeur nulle en premier. Si un cycle existe, fast finit par rattraper slow à l'intérieur du cycle, et ils se rencontrent sur le même nœud. Cette rencontre prouve qu'un cycle existe.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

# Build: 3 -> 2 -> 0 -> -4 -> (back to 2)
nodes = [ListNode(v) for v in [3, 2, 0, -4]]
for i in range(3):
    nodes[i].next = nodes[i+1]
nodes[3].next = nodes[1]   # cycle: -4 -> 2

print(hasCycle(nodes[0]))  # True

Pourquoi les pointeurs lent et rapide se rencontrent toujours

De manière informelle : une fois que les deux pointeurs sont entrés dans le cycle, la distance qui les sépare varie de 1 à chaque étape (fast avance de 2, slow de 1, donc l'écart diminue de 1 à chaque tour). L'écart finit par devenir nul : ils se trouvent sur le même nœud. Plus formellement, si le cycle a une longueur C, l'écart maximal à l'intérieur du cycle est C-1 et il diminue de 1 à chaque étape ; les pointeurs se rencontrent donc dans les C étapes qui suivent au plus leur entrée dans le cycle.

Nombre total d'étapes avant la rencontre : au plus O(n + C) = O(n), puisque C <= n.

# Visualise convergence: simulate gap in cycle
cycle_length = 5
for start_gap in range(1, cycle_length + 1):
    gap = start_gap
    steps = 0
    while gap != 0:
        gap = (gap - 1) % cycle_length
        steps += 1
    print(f'Start gap {start_gap}: meet after {steps} step(s)')

Trouver le point d'entrée du cycle

Après avoir détecté un cycle, l'algorithme de Floyd peut également trouver le nœud d'entrée (l'endroit où commence le cycle). Une fois que slow et fast se sont rencontrés à l'intérieur du cycle, réinitialisez un pointeur sur la tête et laissez l'autre au point de rencontre. Avancez ensuite les deux pointeurs d'une étape à la fois. Ils se rencontreront exactement au nœud d'entrée du cycle. Cela fonctionne parce que la distance entre la tête et l'entrée est égale à la distance entre le point de rencontre et l'entrée, modulo la longueur du cycle.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def detectCycle(head):
    slow = fast = head
    # Phase 1: detect meeting point
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None  # no cycle
    # Phase 2: find entry
    pointer = head
    while pointer is not slow:
        pointer = pointer.next
        slow    = slow.next
    return pointer  # cycle entry node

nodes = [ListNode(v) for v in [3, 2, 0, -4]]
for i in range(3):
    nodes[i].next = nodes[i+1]
nodes[3].next = nodes[1]  # entry is nodes[1] (val=2)

entry = detectCycle(nodes[0])
print(entry.val)  # 2

Preuve mathématique du nœud d'entrée

Soit F = distance entre la tête et l'entrée du cycle, C = longueur du cycle et a = distance entre l'entrée et le point de rencontre à l'intérieur du cycle. Lorsqu'ils se rencontrent, slow a parcouru F + a étapes ; fast a parcouru F + a + n*C étapes (n tours complets d'avance). Comme fast = 2 * slow : 2(F+a) = F+a+nC → F = nC - a. Cela signifie que la distance entre la tête et l'entrée est égale à la distance entre le point de rencontre et l'entrée, modulo C. Réinitialiser un pointeur sur la tête et avancer les deux pointeurs de 1 les fait converger au nœud d'entrée.

# Verify with our example: F=1 (head to node 2), C=3 (cycle: 2->0->-4->2), a=?
# Meeting inside cycle after F+a slow steps
# Let us measure a by counting from entry to meeting point
# In practice the code handles this automatically
F = 1   # head(3) to entry(2)
C = 3   # cycle length 2->0->-4
# n=1: F = 1*C - a => a = C - F = 3 - 1 = 2
a = C - F
print(f'F={F}, C={C}, a={a}')
print(f'After meeting, {F} more steps reach entry: {F == C - a or F % C == (C - a) % C}')

Mesurer la longueur du cycle

Une fois le point de rencontre situé dans le cycle obtenu (phase 1 de l'algorithme de Floyd), vous pouvez mesurer la longueur du cycle : maintenez un pointeur immobile et avancez l'autre jusqu'à ce qu'ils se rencontrent à nouveau. Le nombre d'étapes effectuées correspond à la longueur du cycle. Cette méthode est utile pour les problèmes qui demandent explicitement cette longueur.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def cycle_length(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:  # found meeting point
            length = 1
            fast = fast.next
            while fast is not slow:
                fast = fast.next
                length += 1
            return length
    return 0  # no cycle

nodes = [ListNode(v) for v in [1, 2, 3, 4, 5]]
for i in range(4):
    nodes[i].next = nodes[i+1]
nodes[4].next = nodes[2]  # cycle: 3->4->5->3, length=3
print(cycle_length(nodes[0]))  # 3

Nombre heureux (détection de cycle sans liste)

L'algorithme de Floyd ne se limite pas aux listes chaînées. LeetCode 202, « Nombre heureux », demande si le remplacement répété de n par la somme des carrés de ses chiffres finit par atteindre 1. Si le processus entre dans un cycle qui n'inclut pas 1, il tournera indéfiniment. Vous pouvez le modéliser comme le parcours d'une liste chaînée virtuelle, où le « suivant » de chaque nœud est la valeur calculée suivante, puis appliquer l'algorithme de Floyd pour détecter le cycle.

def isHappy(n):
    def next_val(x):
        total = 0
        while x:
            x, d = divmod(x, 10)
            total += d * d
        return total

    slow, fast = n, next_val(n)
    while fast != 1 and slow != fast:
        slow = next_val(slow)
        fast = next_val(next_val(fast))
    return fast == 1

print(isHappy(19))  # True  (1->81+1=82->68->100->1)
print(isHappy(2))   # False (enters cycle)

Détection naïve par ensemble ou par l'algorithme de Floyd

L'approche fondée sur un ensemble stocke chaque nœud parcouru dans un ensemble et vérifie son appartenance avant de le parcourir. Elle est en O(n) de temps et O(n) d'espace. L'algorithme de Floyd est également en O(n) de temps, mais n'utilise qu'un espace O(1) — aucune structure de données supplémentaire. Dans les environnements où la mémoire est limitée (systèmes embarqués, noyaux de systèmes d'exploitation), la garantie d'un espace O(1) est importante. Lors d'un entretien, on vous demandera parfois explicitement un espace O(1) après que vous aurez proposé la solution fondée sur un ensemble.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Naive O(n) space approach
def hasCycle_set(head):
    seen = set()
    while head:
        if id(head) in seen:
            return True
        seen.add(id(head))
        head = head.next
    return False

# Floyd's O(1) space approach
def hasCycle_floyd(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

print('Both implementations give the same result')

Cas limites de la détection de cycles

Trois cas limites doivent être pris en compte. Premièrement, la liste vide : head is None — la condition de boucle de Floyd fast and fast.next provoque immédiatement la sortie de la boucle, qui renvoie False. Deuxièmement, un nœud unique sans cycle : fast.next vaut None, la boucle se termine et renvoie False. Troisièmement, un nœud unique avec un cycle : le pointeur next du nœud pointe vers lui-même ; slow et fast commencent tous deux sur head. Après une étape, fast avance vers head.next.next = head, tandis que slow se trouve sur head.next = head. fast == slow dès la toute première itération.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

# Edge cases
print(hasCycle(None))               # False: empty
node = ListNode(1)
print(hasCycle(node))               # False: single, no cycle
node.next = node
print(hasCycle(node))               # True: single node cycle

Cycle de liste chaînée II : LeetCode 142

LeetCode 142, « Cycle de liste chaînée II », demande le nœud où commence le cycle (ou aucune valeur s'il n'y a pas de cycle). Il s'agit de l'application directe de l'algorithme de Floyd en deux phases. Les personnes qui mènent les entretiens posent cette question après la détection de cycles élémentaire. La solution complète est la suivante : la phase 1 trouve le point de rencontre à l'intérieur du cycle ; la phase 2 réinitialise un pointeur sur la tête et fait avancer les deux pointeurs jusqu'à leur rencontre — ce point de rencontre est l'entrée du cycle.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def detectCycle(head):
    slow = fast = head
    # Phase 1
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None
    # Phase 2
    ptr = head
    while ptr is not slow:
        ptr  = ptr.next
        slow = slow.next
    return ptr

nodes = [ListNode(v) for v in [1, 2, 3, 4, 5]]
for i in range(4):
    nodes[i].next = nodes[i+1]
nodes[4].next = nodes[2]  # cycle entry: node with val=3
entry = detectCycle(nodes[0])
print(entry.val)  # 3

Pourquoi Floyd est meilleur que l'approche par ensemble

Bien que les deux approches soient en O(n) de temps, leur facteur constant diffère en pratique. L'approche par ensemble doit hacher le pointeur de chaque nœud (calculer le hachage, sonder la table de hachage et stocker le pointeur), tandis que l'algorithme de Floyd n'effectue que des déréférencements de pointeurs, bien moins coûteux à chaque étape. Plus important encore, la garantie d'un espace O(1) permet à l'algorithme de Floyd de traiter des listes de longueur arbitraire sans risquer de manquer de mémoire.

Mentionner spontanément cet avantage en matière d'espace lors d'un entretien montre une compréhension approfondie des compromis algorithmiques, au-delà de la seule notation de la complexité en grand O.

Vérification rapide

Évaluez votre compréhension des concepts de Structures de données et algorithmes — Préparation aux entretiens de programmation présentés dans cette leçon.

Récapitulatif de la leçon

Dans cette leçon, vous avez appris que : l'algorithme des pointeurs lent et rapide de Floyd détecte les cycles en O(n) de temps et avec un espace O(1), la phase 2 (réinitialiser un pointeur sur la tête et avancer les deux de 1) trouve le nœud d'entrée exact du cycle, et la même technique s'applique au-delà des listes chaînées à toute séquence implicite où le « suivant » est une fonction. Nous allons maintenant voir la fusion de listes triées, la séparation des listes à leur point médian et la recherche du nœud en n-ième position depuis la fin.

Questions Fréquemment Posées

La leçon « Détection de cycles avec l’algorithme de Floyd » est-elle gratuite ?

Oui — le texte complet de « Détection de cycles avec l’algorithme de Floyd » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Détection de cycles avec l’algorithme de Floyd » ?

Détectez les cycles avec l’approche des pointeurs lent et rapide, trouvez le point d’entrée du cycle et démontrez mathématiquement la correction de l’algorithme. Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?

Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.

Combien de temps prend la leçon « Détection de cycles avec l’algorithme de Floyd » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?

Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Classe Node et construction de listes
  2. Inverser une liste chaînée
  3. Détection de cycles avec l’algorithme de Floyd
  4. Fusionner, scinder et trouver le n-ième élément depuis la fin
← Retour à DSA Interview Prep