Rilevamento dei cicli con l'algoritmo di Floyd
Rilevi i cicli con l'approccio dei puntatori lento e veloce, trovi il punto d'ingresso del ciclo e dimostri matematicamente la correttezza dell'algoritmo
Rilevamento dei cicli con l'algoritmo di Floyd è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Che cos'è un ciclo in una lista concatenata?
Un ciclo in una lista concatenata si verifica quando il puntatore next di un nodo punta a un nodo già visitato, creando un ciclo infinito. Attraversare una lista di questo tipo con un ciclo while head non terminerebbe mai. Il rilevamento dei cicli è un classico problema da colloquio e costituisce la base di algoritmi più avanzati sui puntatori.
L'approccio ingenuo memorizza ogni nodo visitato in un set e ne verifica l'appartenenza: O(n) di tempo e O(n) di spazio. L'algoritmo di Floyd risolve lo stesso problema in O(n) di tempo e O(1) di spazio, che è ciò che gli intervistatori si aspettano.
Algoritmo dei puntatori lento e veloce di Floyd
Il rilevamento dei cicli di Floyd (la «tartaruga e la lepre») utilizza due puntatori: slow avanza di un passo alla volta, mentre fast avanza di due passi. Se non esiste alcun ciclo, fast raggiunge None per primo. Se esiste un ciclo, fast raggiunge infine slow all'interno del ciclo e i due puntatori si incontrano nello stesso nodo. L'incontro dimostra che esiste un ciclo.
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])) # TruePerché lento e veloce si incontrano sempre
In termini intuitivi: una volta che entrambi i puntatori sono entrati nel ciclo, la distanza tra loro cambia di 1 a ogni passo (fast guadagna 2 posizioni, slow 1, quindi il divario si riduce di 1 a ogni iterazione). Alla fine il divario diventa 0: i due puntatori si trovano nello stesso nodo. Più formalmente, se il ciclo ha lunghezza C, il divario massimo al suo interno è C-1 e si riduce di 1 a ogni passo; pertanto i puntatori si incontrano entro C passi da quando entrambi sono entrati nel ciclo.
Passi totali prima dell'incontro: al massimo O(n + C) = O(n), poiché 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)')Trovare il punto di ingresso del ciclo
Dopo aver rilevato un ciclo, l'algoritmo di Floyd può anche trovare il nodo di ingresso (dove inizia il ciclo). Dopo che slow e fast si sono incontrati all'interno del ciclo, si riporti un puntatore alla testa e si lasci l'altro nel punto d'incontro. Quindi si facciano avanzare entrambi di un passo alla volta. Si incontreranno esattamente nel nodo di ingresso del ciclo. Questo funziona perché la distanza dalla testa all'ingresso coincide con la distanza dal punto d'incontro all'ingresso (modulo la lunghezza del ciclo).
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) # 2Dimostrazione matematica del nodo di ingresso
Sia F = distanza dalla testa all'ingresso del ciclo, C = lunghezza del ciclo e a = distanza dall'ingresso al punto d'incontro all'interno del ciclo. Quando si incontrano: slow ha percorso F + a passi; fast ha percorso F + a + n*C passi (n giri completi in più). Poiché fast = 2 * slow: 2(F+a) = F+a+nC → F = nC - a. Ciò significa che la distanza dalla testa all'ingresso è uguale alla distanza dal punto d'incontro all'ingresso (modulo C). Riportando un puntatore alla testa e facendo avanzare entrambi di 1, i due puntatori convergono nel nodo di ingresso.
# 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}')Misurare la lunghezza del ciclo
Una volta ottenuto il punto d'incontro all'interno del ciclo (fase 1 dell'algoritmo di Floyd), è possibile misurare la lunghezza del ciclo: si mantenga fermo un puntatore e si faccia avanzare l'altro finché non si incontrano nuovamente. Il numero di passi effettuati è uguale alla lunghezza del ciclo. Questo è utile per i problemi che richiedono esplicitamente la lunghezza del ciclo.
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])) # 3Numero felice (rilevamento dei cicli senza una lista)
L'algoritmo di Floyd non è limitato alle liste concatenate. LeetCode 202, «Happy Number», chiede di determinare se la sostituzione ripetuta di n con la somma dei quadrati delle sue cifre raggiunga infine 1. Se n entra in un ciclo che non include 1, il processo continuerà all'infinito. È possibile modellare questo processo come l'attraversamento di una lista concatenata virtuale, in cui il «next» di ogni nodo è il valore calcolato successivo, e quindi applicare l'algoritmo di Floyd per rilevare il ciclo.
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)Rilevamento ingenuo basato su un set a confronto con Floyd
L'approccio basato su un set memorizza ogni nodo visitato in un set e ne verifica l'appartenenza prima di visitarlo. Ha complessità O(n) in termini di tempo e O(n) in termini di spazio. L'algoritmo di Floyd ha anch'esso complessità O(n) in termini di tempo, ma utilizza soltanto O(1) di spazio, senza alcuna struttura dati aggiuntiva. In ambienti con memoria limitata, come i sistemi embedded e i kernel dei sistemi operativi, la garanzia di O(1) di spazio è importante. A volte gli intervistatori chiedono esplicitamente O(1) di spazio come approfondimento dopo aver ricevuto la soluzione con il set.
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')Casi limite nel rilevamento dei cicli
È necessario gestire tre casi limite. Primo, lista vuota: head is None; la condizione del ciclo di Floyd, fast and fast.next, termina immediatamente e restituisce False. Secondo, un solo nodo senza ciclo: fast.next è None, il ciclo termina e restituisce False. Terzo, un solo nodo con un ciclo: il puntatore next del nodo punta a se stesso; slow e fast iniziano entrambi dalla testa. Dopo un passo, fast avanza a head.next.next = head, mentre slow si trova in head.next = head. Quindi fast == slow già alla prima iterazione.
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 cycleCiclo nella lista concatenata II: LeetCode 142
LeetCode 142, «Linked List Cycle II», richiede il nodo in cui inizia il ciclo (oppure None se non esiste alcun ciclo). Questa è l'applicazione diretta dell'algoritmo di Floyd in due fasi. Gli intervistatori lo propongono come approfondimento dopo il problema base del rilevamento dei cicli. La soluzione completa è la seguente: la fase 1 trova il punto d'incontro all'interno del ciclo; la fase 2 riporta un puntatore alla testa e fa avanzare entrambi in avanti finché non si incontrano: quel punto d'incontro è l'ingresso del ciclo.
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) # 3Perché Floyd è migliore dell'approccio con un set
Sebbene entrambi gli approcci abbiano complessità O(n) in termini di tempo, nella pratica il fattore costante è diverso. L'approccio con un set deve calcolare l'hash del puntatore di ogni nodo (calcolare l'hash, sondare la tabella hash e memorizzare il puntatore), mentre l'algoritmo di Floyd esegue soltanto dereferenziazioni di puntatori, molto meno costose per ogni passo. Ancora più importante, la garanzia di O(1) di spazio consente all'algoritmo di Floyd di operare su liste di lunghezza arbitraria senza il rischio di esaurire la memoria.
Menzionare spontaneamente questo vantaggio in termini di spazio durante un colloquio dimostra una comprensione approfondita dei compromessi algoritmici che va oltre la semplice notazione Big-O.
Verifica rapida
Verifichi la propria comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: l'algoritmo dei puntatori lento e veloce di Floyd rileva i cicli in O(n) di tempo e O(1) di spazio, la fase 2 (riportare un puntatore alla testa e far avanzare entrambi di 1) trova l'esatto nodo di ingresso del ciclo e la stessa tecnica si applica anche oltre le liste concatenate, a qualsiasi sequenza implicita in cui «next» sia una funzione. Ora esamineremo l'unione di liste ordinate, la suddivisione delle liste in corrispondenza del punto centrale e la ricerca del nodo n-esimo dalla fine.
Domande Frequenti
La lezione «Rilevamento dei cicli con l'algoritmo di Floyd» è gratuita?
Sì — il testo completo di «Rilevamento dei cicli con l'algoritmo di Floyd» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Rilevamento dei cicli con l'algoritmo di Floyd»?
Rilevi i cicli con l'approccio dei puntatori lento e veloce, trovi il punto d'ingresso del ciclo e dimostri matematicamente la correttezza dell'algoritmo Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Rilevamento dei cicli con l'algoritmo di Floyd»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Classe Node e costruzione delle liste
- Invertire una linked list
- Rilevamento dei cicli con l'algoritmo di Floyd
- Unire, dividere e trovare l'ennesimo elemento dalla fine