Detección de ciclos con el algoritmo de Floyd
Detecte ciclos mediante el enfoque de punteros lento y rápido, encuentre el punto de entrada del ciclo y demuestre matemáticamente la corrección del algoritmo.
Detección de ciclos con el algoritmo de Floyd es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué es un ciclo en una lista enlazada?
Un ciclo en una lista enlazada se produce cuando el puntero next de un nodo apunta a un nodo visitado anteriormente, lo que crea un bucle infinito. Recorrer una lista así con un bucle while head no terminaría nunca. La detección de ciclos es un problema clásico de las entrevistas y la base de algoritmos de punteros más avanzados.
El enfoque ingenuo almacena cada nodo visitado en un conjunto y comprueba si pertenece a él: tiempo O(n) y espacio O(n). El algoritmo de Floyd resuelve el mismo problema en tiempo O(n) y con espacio O(1), que es lo que esperan los entrevistadores.
Algoritmo de punteros lento y rápido de Floyd
La detección de ciclos de Floyd (la «tortuga y la liebre») utiliza dos punteros: slow avanza un paso cada vez y fast avanza dos pasos. Si no existe ningún ciclo, fast llega primero a None. Si existe un ciclo, fast acaba alcanzando a slow dentro del ciclo y ambos se encuentran en el mismo nodo. El encuentro demuestra que existe 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])) # TruePor qué los punteros lento y rápido siempre se encuentran
De forma intuitiva: una vez que ambos punteros entran en el ciclo, la distancia entre ellos cambia en 1 por paso (fast avanza 2 y slow avanza 1, por lo que la diferencia se reduce en 1 en cada ronda). Finalmente, la diferencia llega a 0: ambos están en el mismo nodo. De forma más formal, si el ciclo tiene longitud C, la diferencia máxima dentro del ciclo es C-1 y se reduce en 1 en cada paso, por lo que ambos se encuentran en un máximo de C pasos después de que los dos hayan entrado en el ciclo.
Total de pasos antes del encuentro: como máximo O(n + C) = O(n), ya que 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)')Encontrar el punto de entrada del ciclo
Después de detectar un ciclo, el algoritmo de Floyd también puede encontrar el nodo de entrada (donde comienza el ciclo). Cuando slow y fast se encuentren dentro del ciclo, reinicie un puntero en la cabeza y deje el otro en el punto de encuentro. Después, avance ambos un paso cada vez. Se encontrarán exactamente en el nodo de entrada del ciclo. Esto funciona porque la distancia desde la cabeza hasta la entrada es igual a la distancia desde el punto de encuentro hasta la entrada (módulo la longitud 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) # 2Demostración matemática del nodo de entrada
Sea F = distancia desde la cabeza hasta la entrada del ciclo, C = longitud del ciclo y a = distancia desde la entrada hasta el punto de encuentro dentro del ciclo. Cuando se encuentran, slow ha recorrido F + a pasos y fast ha recorrido F + a + n*C pasos (n vueltas completas por delante). Como fast = 2 * slow: 2(F+a) = F+a+nC → F = nC - a. Esto significa que la distancia desde la cabeza hasta la entrada es igual a la distancia desde el punto de encuentro hasta la entrada (módulo C). Al reiniciar un puntero en la cabeza y avanzar ambos 1 paso cada vez, convergen en el nodo de entrada.
# 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}')Medición de la longitud del ciclo
Una vez que tenga el punto de encuentro dentro del ciclo (la fase 1 del algoritmo de Floyd), puede medir la longitud del ciclo: mantenga un puntero inmóvil y avance el otro hasta que vuelvan a encontrarse. El número de pasos realizados equivale a la longitud del ciclo. Esto resulta útil en problemas que solicitan explícitamente la longitud 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])) # 3Número feliz (detección de ciclos sin una lista)
El algoritmo de Floyd no se limita a las listas enlazadas. LeetCode 202 'Happy Number' pregunta si al reemplazar repetidamente n por la suma de los cuadrados de sus dígitos se llega finalmente a 1. Si entra en un ciclo que no incluye 1, continuará en un bucle infinito. Puede modelar esto como un recorrido virtual de una lista enlazada en la que el 'next' de cada nodo es el siguiente valor calculado; después, aplique el algoritmo de Floyd para detectar el 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)Detección ingenua basada en conjuntos frente a Floyd
El enfoque basado en conjuntos almacena cada nodo visitado en un conjunto y comprueba si pertenece a él antes de visitarlo. Tiene tiempo O(n) y espacio O(n). Floyd también tiene tiempo O(n), pero solo utiliza espacio O(1), sin ninguna estructura de datos adicional. En entornos con memoria limitada (sistemas embebidos y núcleos de sistemas operativos), la garantía de espacio O(1) es importante. A veces los entrevistadores solicitan explícitamente espacio O(1) como pregunta de seguimiento después de que usted presente la solución basada en conjuntos.
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')Casos límite para la detección de ciclos
Hay que gestionar tres casos límite. Primero, lista vacía: head is None; la condición del bucle de Floyd fast and fast.next termina inmediatamente y devuelve False. Segundo, un solo nodo sin ciclo: fast.next es None, el bucle termina y devuelve False. Tercero, un solo nodo con ciclo: el next del nodo apunta a sí mismo; slow y fast comienzan en head. Después de un paso, fast avanza hasta head.next.next = head, pero slow está en head.next = head. Por tanto, fast == slow ya en la primera iteración.
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 de lista enlazada II: LeetCode 142
LeetCode 142 'Linked List Cycle II' solicita el nodo donde comienza el ciclo (o None si no existe). Esta es la aplicación directa del algoritmo de Floyd en dos fases. Los entrevistadores lo plantean como continuación de la detección básica de ciclos. La solución completa es la siguiente: la fase 1 encuentra el punto de encuentro dentro del ciclo; la fase 2 reinicia un puntero en la cabeza y avanza ambos hacia delante hasta que se encuentran; ese punto de encuentro es la entrada 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) # 3Por qué Floyd supera al enfoque basado en conjuntos
Aunque ambos enfoques tienen tiempo O(n), el factor constante difiere en la práctica. El enfoque basado en conjuntos debe aplicar hash al puntero de cada nodo (calcular el hash, consultar la tabla hash y almacenar el puntero), mientras que Floyd solo realiza desreferencias de punteros, que son mucho más económicas en cada paso. Más importante aún, la garantía de espacio O(1) permite que Floyd se ejecute con listas de cualquier longitud sin riesgo de quedarse sin memoria.
Mencionar proactivamente esta ventaja de espacio en una entrevista demuestra una comprensión profunda de las compensaciones algorítmicas que va más allá de la notación Big-O básica.
Comprobación rápida
Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido que: el algoritmo de punteros lento y rápido de Floyd detecta ciclos en tiempo O(n) y espacio O(1), la fase 2 (reiniciar un puntero en la cabeza y avanzar ambos 1 paso) encuentra el nodo exacto de entrada del ciclo, y la misma técnica se aplica más allá de las listas enlazadas a cualquier secuencia implícita en la que 'next' sea una función. A continuación veremos cómo fusionar listas ordenadas, dividir listas por sus puntos medios y encontrar el nodo n desde el final.
Preguntas frecuentes
¿La lección «Detección de ciclos con el algoritmo de Floyd» es gratis?
Sí — el texto completo de «Detección de ciclos con el algoritmo de Floyd» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Detección de ciclos con el algoritmo de Floyd»?
Detecte ciclos mediante el enfoque de punteros lento y rápido, encuentre el punto de entrada del ciclo y demuestre matemáticamente la corrección del algoritmo. Practicas DSA Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar DSA Interview Prep?
No se requiere experiencia previa. DSA Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «Detección de ciclos con el algoritmo de Floyd»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de DSA Interview Prep?
Sí. Cada lección de DSA Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Clase Node y construcción de listas
- Inversión de una lista enlazada
- Detección de ciclos con el algoritmo de Floyd
- Combinar, dividir y encontrar el enésimo elemento desde el final