0Pricing
Coding Interview Prep · Lección

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 Coding 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 Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding 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]))  # True

Por 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)  # 2

Demostració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]))  # 3

Nú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 cycle

Ciclo 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)  # 3

Por 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 Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding 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 Coding 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 Coding Interview Prep?

No se requiere experiencia previa. Coding 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 Coding Interview Prep?

Sí. Cada lección de Coding 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

  1. Clase Node y construcción de listas
  2. Inversión de una lista enlazada
  3. Detección de ciclos con el algoritmo de Floyd
  4. Combinar, dividir y encontrar el enésimo elemento desde el final
← Volver a Coding Interview Prep