Saltar al contenido

Ciclo en una cadena

Fácil#fast-slow-pointers#cycle-detection~15 min

La misión

Problema

Recibes la cabeza de una cadena de nodos simplemente enlazada. En algún punto, un nodo puede apuntar de vuelta a un nodo anterior, lo que hace que el recorrido dé vueltas para siempre en lugar de llegar al final. Devuelve True si la cadena contiene un ciclo así y False si, siguiendo los enlaces, tarde o temprano llegas a None. En los ejemplos, la cadena se describe con sus valores más pos, el índice al que enlaza de vuelta el último nodo, o -1 si no hay ciclo.

Ejemplos

Input:  values = [3, 2, 0, -4], pos = 1
Output: True
Por qué: el último nodo enlaza de vuelta al nodo que guarda 2
Input:  values = [1, 2], pos = -1
Output: False
Por qué: el recorrido termina después del segundo nodo
Input:  values = [7], pos = 0
Output: True
Por qué: caso límite: un único nodo que se apunta a sí mismo

Pistas

0 / 3

Tiempo objetivo
O(n)
Espacio objetivo
O(1)

¿Lo que te frena es la idea y no el código? Detectar un ciclo lo explica.

Python 3Ctrl+Enter ejecuta