Dos punteros: lento y rápido

El patrón de punteros lento-rápido, también llamado tortuga y liebre, utiliza dos punteros que avanzan a distintas velocidades por la misma secuencia. A diferencia de los punteros en extremos opuestos, ambos comienzan al principio. El puntero lento avanza un paso cada vez; el rápido avanza dos pasos, o más. Esta diferencia de velocidad crea invariantes útiles: el puntero lento sigue el rastro de un «prefijo válido», mientras el rápido busca condiciones más adelante.

En un arreglo ordenado, los duplicados son adyacentes. El puntero lento sigue el último valor único escrito; el puntero rápido explora los elementos siguientes. Cuando el puntero rápido llega a un valor diferente de nums[slow], incremente slow y copie el nuevo valor. Este algoritmo sobre el mismo arreglo se ejecuta en O(n) con O(1) de espacio adicional; es una pregunta habitual de entrevistas que evalúa el dominio del patrón de punteros de lectura y escritura.

Mueva todos los ceros al final y conserve el orden relativo de los elementos distintos de cero. El puntero lento indica la siguiente posición para un elemento distinto de cero. El puntero rápido busca valores distintos de cero. Cuando fast encuentra uno, cópielo en la posición de slow y haga avanzar ambos punteros. Después del recorrido, rellene con ceros las posiciones desde slow hasta el final. Tiempo O(n) y espacio O(1).

El subpaso de partición de quicksort reorganiza los elementos en el mismo arreglo, de modo que todos los valores < pivot queden antes que los valores >= pivot. El esquema de Lomuto utiliza un puntero lento, que marca la última posición de un elemento pequeño, y un puntero rápido, que recorre el arreglo hacia delante. Cuando fast encuentra un elemento pequeño, incremente slow e intercambie los elementos. Se ejecuta en O(n) con O(1) de espacio adicional.

Con punteros lento-rápido en una lista enlazada, el puntero rápido avanza dos nodos por paso y el lento avanza uno. Cuando fast llega al final, slow se encuentra en el centro. Este enfoque de una sola pasada y O(n) es mucho más limpio que contar los nodos y después recorrer la mitad de la lista. Se utiliza como subpaso en el ordenamiento por mezcla de listas enlazadas y en la detección de palíndromos en listas enlazadas.

La detección de ciclos de Floyd coloca los punteros lento y rápido en el inicio de una lista enlazada. El lento avanza un nodo; el rápido, dos. Si existe un ciclo, el puntero rápido acabará alcanzando al lento y ambos se encontrarán dentro del ciclo. Si fast llega a None, no existe ningún ciclo. El encuentro está garantizado porque fast gana un paso a slow en cada iteración: en un ciclo de longitud k, se encuentran en un máximo de k pasos desde que slow entra en el ciclo.

Después de detectar un ciclo (slow == fast), restablezca uno de los punteros al inicio. Ahora haga avanzar ambos punteros un paso cada vez. Se encontrarán en el punto de entrada del ciclo. Esto utiliza la propiedad matemática de que la distancia desde el inicio hasta la entrada del ciclo es igual a la distancia desde el punto de encuentro hasta la entrada del ciclo, módulo la longitud del ciclo. Es un elegante resultado matemático que aparece con frecuencia en problemas difíciles de entrevistas.

Los punteros lento-rápido también se aplican fuera de las listas enlazadas, a cualquier proceso que forme ciclos. Un «número feliz» recorre una secuencia de sumas de cuadrados de sus dígitos; si n no es feliz, la secuencia acaba entrando en un bucle. Detecte el bucle con slow (un paso = un cuadrado de dígito) y fast (dos pasos). Si se encuentran en 1, n es feliz; de lo contrario, queda atrapado en un ciclo que no contiene 1. Este es el algoritmo de Floyd aplicado a una lista enlazada virtual de valores.

Encuentre el nodo n desde el final de una lista enlazada en una sola pasada utilizando dos punteros. Haga avanzar el puntero rápido n pasos. Después, haga avanzar ambos punteros juntos hasta que fast llegue al final; slow estará entonces en el nodo n desde el final. Para eliminar este nodo, mantenga un puntero «prev» un paso detrás de slow. Este es un problema clásico de listas enlazadas de una sola pasada que evita tener que contar primero la longitud total.

El razonamiento de lento-rápido también se aplica a problemas de arreglos y cadenas. Al comprimir una cadena codificada mediante longitudes de ejecución, el puntero lento marca la posición de escritura y el rápido recorre hasta el final de cada ejecución. Mientras todos los caracteres de la ejecución sean iguales al carácter de slow, haga avanzar fast; de lo contrario, registre la ejecución y actualice slow. Esto logra O(n) en una sola pasada con O(1) de espacio.

Utilice punteros en extremos opuestos cuando el problema incluya pares cuya suma sea un objetivo, comprobaciones de palíndromos o una ventana que se estrecha desde ambos lados. Utilice punteros lento-rápido cuando necesite un puntero de escritura (para eliminar o mover elementos), al procesar la estructura de una lista enlazada (centro o ciclo) o al detectar ciclos en cualquier secuencia de valores. Ambos eliminan los bucles anidados y logran O(n); el factor decisivo es la estructura del recorrido.

Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

En esta lección aprendió que: el patrón lento-rápido (de lectura y escritura) mantiene un puntero de escritura en la siguiente posición válida mientras un puntero rápido recorre el arreglo hacia delante; es la base de las operaciones sobre el mismo arreglo para eliminar, deduplicar y mover ceros; la tortuga y la liebre de Floyd detectan ciclos en O(n) de tiempo y O(1) de espacio aprovechando la diferencia de velocidad entre dos punteros; y después de detectar un ciclo, restablecer un puntero al inicio y hacer avanzar ambos a la misma velocidad encuentra la entrada del ciclo gracias a una igualdad de distancias demostrable. A continuación, exploraremos la API de cadenas de Python para entrevistas.