Ciclo en una cadena
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
Recordar cada nodo que visitas funciona, pero cuesta memoria para toda la cadena. ¿Hay forma de notar un ciclo sin guardar nada?
Imagina dos corredores en una pista, uno el doble de rápido que el otro. En un camino recto nunca vuelven a encontrarse; en uno circular, tienen que hacerlo.
Mueve un puntero de un paso en un paso y otro de dos pasos en dos pasos. Si el rápido se sale por el final, no hay ciclo; si los dos llegan alguna vez al mismo nodo, lo hay.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(1)
Solución
Dos punteros empiezan en la cabeza: uno avanza un enlace por paso y el otro, dos. Sin ciclo, el puntero rápido llega al final y la respuesta es False. Con un ciclo, ambos punteros terminan dando vueltas dentro de él y, como la distancia entre ellos se reduce un enlace en cada paso, el puntero rápido tiene que caer exactamente sobre el lento. El tiempo es O(n) y el espacio es O(1).
class Node:
def __init__(self, val): self.val, self.next = val, None
def build(values, pos): # the tail links back to index pos, or nowhere if -1
nodes = [Node(v) for v in values]
for a, b in zip(nodes, nodes[1:]): a.next = b
if nodes and pos >= 0: nodes[-1].next = nodes[pos]
return nodes[0] if nodes else None
def has_loop(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next # the gap closes by one link per step
if slow is fast:
return True
return False # the fast pointer found the end
print(has_loop(build([3, 2, 0, -4], 1))) # -> True
print(has_loop(build([1, 2], -1))) # -> False
print(has_loop(build([7], 0))) # -> True¿Lo que te frena es la idea y no el código? Detectar un ciclo lo explica.