Detectar un ciclo en una lista enlazada sin memoria: la solución
Pregunta de entrevista para programador, sobre estructuras de datos y complejidad de memoria.
El enunciado
Una lista enlazada es una sucesión de nodos, cada uno de los cuales apunta al siguiente. A veces un nodo apunta a otro ya encontrado: la lista forma entonces un ciclo y nunca termina. ¿Cómo detectar si existe un ciclo sin usar memoria adicional proporcional al tamaño de la lista?
¿Una pista?
Imagina dos corredores que recorren la lista a velocidades distintas: ¿qué ocurre si dan vueltas indefinidamente en un ciclo?
Ver la respuesta y la solución
Respuesta: Algoritmo de Floyd: un puntero avanza un nodo, el otro dos; si se encuentran, hay un ciclo (O(n) en tiempo, O(1) en memoria).
El razonamiento
Bastan dos punteros colocados al principio de la lista: la tortuga avanza un nodo en cada paso, y la liebre, dos nodos. Si la lista termina, la liebre llega al final y se concluye que no hay ciclo. Si existe un ciclo, los dos punteros acaban entrando en él: la liebre alcanza entonces a la tortuga, porque gana un nodo en cada paso, y se encuentran en un mismo nodo. El número de pasos es proporcional al tamaño de la lista, así que la complejidad es O(n) en tiempo. Como solo se almacenan dos punteros, la memoria adicional es O(1).
¿Y ahora?
El razonamiento se entrena como la memoria: practicando a menudo. Ponte a prueba después con nuestros quiz de cultura general.