Algoritmo de detección de ciclo de Floyd en lista enlazada

Se da una lista enlazada cuyo punto de partida se denota por head, y puede haber o no un ciclo presente. Por ejemplo:

Aquí necesitamos hallar el punto C, es decir, el punto de partida del ciclo.

Algoritmo propuesto

El algoritmo se llama algoritmo de ciclo de Floyd o algoritmo de la tortuga y la liebre (Floyd’s Cycle Algorithm / Tortoise and Hare). Para averiguar el punto de partida del ciclo, necesitamos averiguar si siquiera existe un ciclo. Esto involucra dos pasos:

1. Averiguar la presencia del ciclo.
2. Hallar el punto de partida del ciclo.

Paso 1: presencia del ciclo

1. Tomar dos punteros $slow$ y $fast$.
2. Ambos apuntarán inicialmente a la cabeza de la lista enlazada.
3. $slow$ se moverá un paso a la vez.
4. $fast$ se moverá dos pasos a la vez (el doble de velocidad que el puntero $slow$).
5. Comprobar si en algún momento apuntan al mismo nodo antes de que alguno (o ambos) llegue a null.
6. Si apuntan al mismo nodo en cualquier punto de su recorrido, indica que efectivamente existe un ciclo en la lista enlazada.
7. Si obtenemos null, indica que la lista enlazada no tiene ciclo.

Ahora que hemos averiguado si hay un ciclo presente en la lista enlazada, para el siguiente paso necesitamos hallar el punto de partida del ciclo, es decir, C.

Paso 2: punto de partida del ciclo

1. Reiniciar el puntero $slow$ a la cabeza de la lista enlazada.
2. Mover ambos punteros un paso a la vez.
3. El punto en el que se encuentren será el punto de partida del ciclo.

// Presence of cycle
public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
 
    while(fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
        if(slow==fast){
            return true;
        }
    }
 
    return false;
}

// Assuming there is a cycle present and slow and fast are point to their meeting point
slow = head;
while(slow!=fast){
	slow = slow.next;
	fast = fast.next;
}
 
return slow; // the starting point of the cycle.

Por qué funciona

Paso 1: presencia del ciclo

Como el puntero $fast$ se mueve al doble de velocidad que $slow$, podemos decir que en cualquier momento, $fast$ habrá cubierto el doble de distancia que $slow$. También podemos deducir que la diferencia entre la distancia cubierta por ambos punteros aumenta en $1$.

slow: 0 --> 1 --> 2 --> 3 --> 4 (distance covered)
fast: 0 --> 2 --> 4 --> 6 --> 8 (distance covered)
diff: 0 --> 1 --> 2 --> 3 --> 4 (difference between distance covered by both pointers)

Sea $L$ la longitud del ciclo, y $a$ el número de pasos que necesita el puntero lento para llegar a la entrada del ciclo. Existe un entero positivo $k$ ($k > 0$) tal que $k \cdot L \geq a$. Cuando el puntero lento se ha movido $k \cdot L$ pasos, y el puntero rápido ha cubierto $2 \cdot k \cdot L$ pasos, ambos punteros se encuentran dentro del ciclo. En este punto, hay una separación de $k \cdot L$ entre ellos. Dado que la longitud del ciclo sigue siendo $L$, esto significa que se encuentran en el mismo punto dentro del ciclo, resultando en su encuentro.

Paso 2: punto de partida del ciclo

Intentemos calcular la distancia cubierta por ambos punteros hasta el punto en que se encuentran dentro del ciclo.

$slowDist = a + xL + b$ , $x\ge0$

$fastDist = a + yL + b$ , $y\ge0$

• $slowDist$ es la distancia total cubierta por el puntero lento.
• $fastDist$ es la distancia total cubierta por el puntero rápido.
• $a$ es el número de pasos que ambos punteros necesitan dar para entrar al ciclo.
• $b$ es la distancia entre C y G, es decir, la distancia entre el punto de partida del ciclo y el punto de encuentro de ambos punteros.
• $x$ es el número de veces que el puntero lento ha dado vueltas dentro del ciclo, empezando y terminando en C.
• $y$ es el número de veces que el puntero rápido ha dado vueltas dentro del ciclo, empezando y terminando en C.

$fastDist = 2 \cdot (slowDist)$

$a + yL + b = 2(a + xL + b)$

Resolviendo la fórmula obtenemos:

$a=(y-2x)L-b$

donde $y-2x$ es un entero

Esto básicamente significa que $a$ pasos es lo mismo que dar un cierto número de vueltas completas en el ciclo e ir $b$ pasos hacia atrás. Como el puntero rápido ya está $b$ pasos por delante de la entrada del ciclo, si el puntero rápido se mueve otros $a$ pasos terminará en la entrada del ciclo. Y como dejamos que el puntero lento empiece al inicio de la lista enlazada, después de $a$ pasos también terminará en la entrada del ciclo. Así, si ambos se mueven $a$ pasos ambos se encontrarán en la entrada del ciclo.

Problemas:

• Linked List Cycle (EASY) 
• Happy Number (Easy) 
• Find the Duplicate Number (Medium) 
• Linked List Cycle II