Linked List Cycle

Q: ¿Cuál es la complejidad temporal y espacial de detectar un ciclo en una lista enlazada?

Ambos enfoques requieren un tiempo de O(n) , ya que cada nodo se recorre un número limitado de veces. Marcar los nodos visitados requiere O(n) de memoria adicional. Los punteros rápido y lento de Floyd requieren O(1) : dos números de nodo.

Q: ¿Por qué el puntero rápido no puede saltarse el puntero lento?

Dentro del ciclo, en cada ronda fast avanza dos nodos y slow uno, así que la distancia que fast todavía debe recorrer para alcanzar a slow disminuye exactamente en uno. Una distancia que disminuye en uno por ronda sigue la secuencia 3, 2, 1, 0 y no puede pasar de cero, así que los dos punteros se encuentran en un nodo.

Q: ¿Puedes detectar el ciclo contando los pasos?

En esta forma de array, sí: una lista sin ciclo llega a -1 en n enlaces, así que recorrer n enlaces sin llegar al final demuestra que hay un ciclo, con memoria O(1) . Necesita el número de nodos, que una lista formada por punteros no proporciona, y contarlos primero nunca termina si hay un ciclo. El método de Floyd no necesita contar.

FácilPunteros rápido y lento Lista enlazada

+10

Una lista enlazada se almacena en el array next: el nodo i enlaza con el nodo next[i], y -1 significa que la lista termina ahí. La cabeza es el nodo 0. Sigue los enlaces desde la cabeza y devuelve true si vuelves a un nodo que ya habías visitado, o false si llegas al final. Los nodos a los que el recorrido nunca llega no cuentan, aunque se enlacen entre sí formando un ciclo.

Función

hasCycle(next: integer-array) → boolean

nextinteger-array: el enlace de cada nodo: next[i] es el nodo que está después del nodo i, o -1
Devuelveboolean: verdadero si el recorrido desde el nodo 0 vuelve a visitar un nodo, falso si llega a -1

Restricciones

1 ≤ next.length ≤ 10⁴
-1 ≤ next[i] ≤ next.length-1
Varios nodos pueden enlazarse al mismo nodo, y algunos nodos pueden ser inaccesibles desde la cabeza.

Ejemplos

Entrada: next = [1, 2, 3, 1]
Salida: true
Explicación: El recorrido va por 0, 1, 2, 3 y después vuelve a 1. El nodo 1 se visita dos veces, así que la lista tiene un ciclo que pasa por los nodos 1, 2 y 3.

Entrada: next = [2, -1, 1]
Salida: false
Explicación: El recorrido pasa por 0, 2, 1 y después llega a -1: tres nodos distintos y después el final, así que no hay ningún ciclo.

Entrada: next = [-1, 2, 1]
Salida: false
Explicación: El nodo 0 enlaza con -1, así que la lista tiene un nodo. Los nodos 1 y 2 se enlazan entre sí en un bucle, pero el recorrido desde la cabeza nunca llega a ellos.

+16 pruebas ocultas al enviar

Para ir más allá

¿También puedes encontrar el nodo donde comienza el ciclo, usando aún memoria extra O(1)?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Una lista sin ciclo llega a -1 en n enlaces, pero una lista con un ciclo nunca termina, así que no puedes esperar hasta el final. Necesitas una forma de detectar que el recorrido está dando vueltas. Recordar cada nodo que visitas lo consigue usando O(n) de memoria. Los punteros rápido y lento de Floyd lo consiguen con dos enteros, porque un puntero que se mueve el doble de rápido debe alcanzar al lento dentro de un bucle.

Marca los nodos que visites

Intuición

Empieza en el nodo 0 y marca cada nodo al salir de él. Si llegas a un nodo que ya está marcado, el recorrido ha vuelto a él y, desde ahí, se repite para siempre: eso es un ciclo. En el ejemplo 1 marcas 0, 1, 2 y 3, y el enlace desde el nodo 3 lleva al nodo 1, que está marcado.

Los nodos están numerados del 0 al n-1, así que un arreglo booleano de longitud n sirve como conjunto de nodos visitados. En una lista enlazada construida con objetos, guardarías las referencias a los nodos en un conjunto hash; la idea es la misma.

Cada nodo se marca como máximo una vez, y el recorrido se detiene en la primera repetición o en -1, así que toma como máximo n pasos: tiempo O(n) y memoria O(n) para las marcas.

Algoritmo

Crea un arreglo booleano visited de longitud n, con todos los valores en false.
Establece node = 0.
Mientras node no sea -1, devuelve true si visited[node] ya es true.
De lo contrario, establece visited[node] y avanza a next[node].
Cuando el recorrido llegue a -1, devuelve false.

def hasCycle(next):
    visited = [False] * len(next)
    node = 0
    while node != -1:
        if visited[node]:
            return True  # back at a node already on the path
        visited[node] = True
        node = next[node]
    return False

Dos punteros, uno rápido y otro lento (detección de ciclos de Floyd)

Intuición

Inicia dos punteros en la cabeza. slow sigue un enlace por ronda y fast sigue dos. Si la lista termina, fast llega primero a -1 y devuelves false. Si hay un ciclo, fast entra primero y sigue dando vueltas hasta que slow también llega.

Una vez que ambos están en el ciclo, en cada ronda fast gana exactamente un nodo a slow. La distancia que fast todavía tiene que recorrer para llegar a slow disminuye en uno en cada ronda, así que llega a cero y los punteros quedan en el mismo nodo. Al ganar un nodo a la vez, fast nunca puede saltarse a slow.

En el ejemplo 1, después de una ronda slow está en el nodo 1 y fast en el nodo 2. Después de dos rondas slow está en el nodo 2 y fast ha pasado por los nodos 3 y 1. Después de tres rondas ambos están en el nodo 3, así que la respuesta es true.

slow necesita como máximo n rondas para entrar en el ciclo y, una vez dentro, se encuentran antes de que complete una vuelta, así que el tiempo es O(n). La única memoria utilizada son dos números de nodo.

Algoritmo

Establece slow = 0 y fast = 0.
Mientras fast no sea -1 y next[fast] no sea -1, mueve slow un enlace y fast dos enlaces.
Después de cada movimiento, devuelve true si están en el mismo nodo.
Cuando el bucle se detenga, fast habrá encontrado el final: devuelve false.

def hasCycle(next):
    slow = 0
    fast = 0
    # fast needs two links to move; if either is missing, the list ends.
    while fast != -1 and next[fast] != -1:
        slow = next[slow]
        fast = next[next[fast]]
        if slow == fast:
            return True
    return False

Errores comunes y casos límite

Los errores aquí tienen que ver con el final de la lista y con qué nodos cuentan.

Mover fast dos enlaces sin comprobar ambos. Tanto fast como next[fast] deben ser nodos reales antes de leer next[next[fast]]; de lo contrario, se lee next[-1], lo que provoca un error en la mayoría de los lenguajes y devuelve silenciosamente el último elemento en Python.
Comparar los punteros antes de moverlos. Ambos empiezan en el nodo 0, así que una comprobación al principio del bucle detecta un ciclo en todas las listas.
Examinar todo el arreglo en lugar del recorrido. En [-1, 2, 1], los nodos 1 y 2 forman un bucle, pero el recorrido desde la cabeza termina enseguida, así que la respuesta es false. También es incorrecto comprobar si se repite un valor en next: en [4, 4, 4, 4, -1], varios nodos enlazan con el nodo 4 y no hay ningún ciclo.
Suponer que un ciclo debe volver a la cabeza. En [1, 2, 3, 4, 4], el último nodo enlaza consigo mismo, y en [0] lo hace la cabeza.

Preguntas frecuentes4

¿Cómo funciona la detección de ciclos de Floyd?

Dos punteros empiezan en la cabeza: uno avanza un enlace por paso y el otro, dos. Sin un ciclo, el rápido llega al final. Con un ciclo, ambos terminan dentro de él; el rápido reduce la distancia en un nodo por paso y se encuentran en el mismo nodo.

¿Cuál es la complejidad temporal y espacial de detectar un ciclo en una lista enlazada?

Ambos enfoques requieren un tiempo de O(n), ya que cada nodo se recorre un número limitado de veces. Marcar los nodos visitados requiere O(n) de memoria adicional. Los punteros rápido y lento de Floyd requieren O(1): dos números de nodo.

¿Por qué el puntero rápido no puede saltarse el puntero lento?

Dentro del ciclo, en cada ronda fast avanza dos nodos y slow uno, así que la distancia que fast todavía debe recorrer para alcanzar a slow disminuye exactamente en uno. Una distancia que disminuye en uno por ronda sigue la secuencia 3, 2, 1, 0 y no puede pasar de cero, así que los dos punteros se encuentran en un nodo.

¿Puedes detectar el ciclo contando los pasos?

En esta forma de array, sí: una lista sin ciclo llega a -1 en n enlaces, así que recorrer n enlaces sin llegar al final demuestra que hay un ciclo, con memoria O(1). Necesita el número de nodos, que una lista formada por punteros no proporciona, y contarlos primero nunca termina si hay un ciclo. El método de Floyd no necesita contar.

Python

def hasCycle(next):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

next = [1, 2, 3, 1]

Esperado

true