Sesión 13: Cracking the Coding Interview (Capítulo 2, Parte 4) — Intersección y Detección de Ciclos en Listas Enlazadas#

Navegación rápida:

← Sesión 12: Sum Lists y Palíndromos
Sesión 14: Consolidación y Simulacro Técnico de Semana 2 →
Glosario Maestro
Guía de Diagramas de Arquitectura
Tiempo estimado de estudio: 60-75 minutos.
Código fuente compilado y probado: practica-rust/dia_13.rs

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

Llegamos al cenit de la manipulación de listas enlazadas: la topología en forma de "Y" (intersección) y las estructuras con ciclos cerrados (anillos). Consulta el Glosario Maestro.

Intersección por Referencia vs por Valor#

(a) En palabras simples (intuición): Dos ríos distintos que se unen en una sola corriente. A partir del punto de unión, el agua viaja por el mismo cauce. No significa que dos ríos tengan peces parecidos; significa que literalmente comparten la misma agua.
(b) Definición técnica paso a paso: Dos listas enlazadas intersectan si y solo si convergen físicamente en el mismo nodo de memoria RAM: node_a as *const ListNode == node_b as *const ListNode. A partir de ese nodo común, todos los nodos subsiguientes hasta la cola son idénticos.
(c) Cómo funciona en Rust (memoria y tipos): La identidad no se evalúa con val == val (igualdad de datos), sino comparando la dirección física en memoria con punteros crudos o comparando índices de nodo en un Arena (idx_a == idx_b).
(d) Error típico de Junior: Recorrer las listas comparando val == val y concluir falsamente que intersectan solo porque dos nodos independientes casualmente almacenan el número 7.

Conmutación de Punteros (Two Pointers Alignment)#

(a) En palabras simples (intuición): Dos amigos corren en pistas de carreras de longitudes diferentes. Para que ambos recorran exactamente la misma distancia total, el que termina la pista A pasa a correr la pista B, y el que termina la pista B pasa a correr la pista A. Al completar ambas pistas, se cruzan exactamente en el mismo instante.
(b) Definición técnica paso a paso: Técnica matemática para hallar la intersección de dos listas de longitudes desconocidas $L₁$ y $L₂$ en una sola pasada. El puntero $A$ recorre $L₁$ y luego salta a la cabeza de $L₂$ . El puntero $B$ recorre $L₂$ y luego salta a la cabeza de $L₁$ . Ambos recorren exactamente $L₁ + L₂$ pasos, sincronizándose en la intersección en $O(N + M)$ tiempo y $O(1)$ memoria.
(c) Cómo funciona en Rust (memoria y tipos): Se implementa limpiamente sobre un Arena mediante expresiones match que reasignan el índice de nodo cuando se llega a None.
(d) Error típico de Junior: Olvidar que si las listas no intersectan jamás, ambos punteros llegarán a None al mismo tiempo, lo que debe terminar el bucle de forma segura sin ciclarse infinitamente.

Algoritmo de Detección de Ciclos de Floyd (Tortoise and Hare)#

(a) En palabras simples (intuición): La Liebre corre al doble de velocidad que la Tortuga en una pista circular cerrada. Como la Liebre es más rápida, le dará una vuelta completa de ventaja y terminará alcanzando a la Tortuga por detrás.
(b) Definición técnica paso a paso: Algoritmo que detecta ciclos en grafos dirigidos funcionales mediante dos punteros: la Tortuga (slow) avanza 1 paso por iteración y la Liebre (fast) avanza 2 pasos. Si existe un ciclo, la distancia relativa entre ambos disminuye en 1 en cada iteración, garantizando una colisión física dentro del ciclo en tiempo $O(N)$ y espacio $O(1)$ .
(c) Cómo funciona en Rust (memoria y tipos): En Rust puro, los ciclos no pueden representarse con Box porque violan la propiedad exclusiva. Se modelan formalmente con una lista indexada en Arena (Vec<ArenaNode>), donde los ciclos se construyen apuntando nodes[tail].next = Some(cycle_start_idx).
(d) Error típico de Junior: Usar un HashSet para guardar nodos visitados ( $O(N)$ espacio auxiliar en Heap) en lugar del algoritmo de Floyd ( $O(1)$ espacio).

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

La Matemática de Floyd: Demostración Formal del Punto de Inicio del Ciclo (LeetCode 142)#

Esta es una de las demostraciones matemáticas más elegantes de las ciencias de la computación.

TEXT

Pista de Carrera:
[Inicio] ----(k pasos)----> [Inicio Ciclo] ----(m pasos)----> [Punto de Encuentro]
                                  ^                                    |
                                  |------------(C - m pasos)-----------|

Definamos las variables físicas:

$k$ : Longitud del camino recto antes de entrar al ciclo.
$C$ : Longitud del ciclo (número de nodos dentro del anillo).
$m$ : Distancia desde el inicio del ciclo hasta el punto exacto donde la Liebre alcanza a la Tortuga.

Fase 1: La Colisión#

Cuando la Tortuga llega al inicio del ciclo, ha recorrido $k$ pasos. En ese mismo instante, la Liebre ya ha recorrido $2k$ pasos y se encuentra dentro del ciclo. A partir de ahí, en cada iteración la Liebre se acerca 1 paso a la Tortuga ( $2 - 1 = 1$ ). Cuando colisionan:

Distancia recorrida por la Tortuga:

D_{slow} = k + m

Distancia recorrida por la Liebre (que corrió al doble de velocidad):

D_{fast} = 2 · D_{slow} = 2(k + m) = 2k + 2m

Pero la Liebre solo pudo alcanzar a la Tortuga completando un número entero de vueltas completas $P$ dentro del ciclo:

D_{fast} = D_{slow} + P · C ⟹ 2(k + m) = (k + m) + P · C

Restando $(k + m)$ a ambos lados:

k + m = P \cdot C ⟹ k = P \cdot C - m = (P - 1)C + (C - m)

Fase 2: Localización del Inicio del Ciclo#

¡Observa con detenimiento la ecuación matemática final: $k = (P - 1)C + (C - m)$ !

La distancia desde el Inicio de la lista hasta el Inicio del ciclo es exactamente $k$ .
La distancia desde el Punto de Encuentro hasta el Inicio del ciclo (completando la vuelta) es exactamente $C - m$ .
Como $k \equiv C - m \pmod C$ , ¡ambas distancias son matemáticamente idénticas!

Por lo tanto:

Dejamos un puntero $P₁$ en el Punto de Encuentro.
Colocamos un puntero $P₂$ en la Cabeza de la lista.
Hacemos que ambos avancen a la misma velocidad (1 paso a la vez).
Cuando ambos hayan caminado exactamente $k$ pasos, $P₁$ y $P₂$ colisionarán con certeza absoluta en el nodo de inicio del ciclo.

3. Visualización Paso a Paso y Gráfica de Memoria en Rust#

Flujo de Detección de Ciclo de Floyd#

Consulta la visualización vectorial de arquitectura:

Gráfico SVG: ![Visualización del Día 13 y Memoria en Rust](../diagrams/sesiones/dia_13.svg)
Enlace al código fuente Mermaid: Fuente Mermaid

DIAGRAMA MERMAID

flowchart LR
    N1["[1] (Inicio)"] --> N2["[2]"]
    N2 --> N3["[3] (Inicio Ciclo)"]
    N3 --> N4["[4]"]
    N4 --> N5["[5] (Colisión Liebre/Tortuga)"]
    N5 --> N6["[6]"]
    N6 --> N3

Visualización Cuadro por Cuadro: Conmutación de Punteros en Intersección (CTCI 2.7)#

Lista A (longitud 5): 1 -> 2 -> [100 -> 200 -> None] (2 nodos únicos + 2 compartidos). Lista B (longitud 4): 9 -> [100 -> 200 -> None] (1 nodo único + 2 compartidos).

TEXT

PASO 1: Recorrido independiente
- pA recorre Lista A: 1, 2, 100, 200, None.
- pB recorre Lista B: 9, 100, 200, None.

PASO 2: Conmutación de cabezas
- Cuando pB llega a None (en paso 3), salta a la cabeza de Lista A (nodo 1).
- Cuando pA llega a None (en paso 4), salta a la cabeza de Lista B (nodo 9).

PASO 3: Encuentro sincronizado
- Distancia total recorrida por pA: 4 nodos de A + 1 nodo de B = 5 nodos.
- Distancia total recorrida por pB: 3 nodos de B + 2 nodos de A = 5 nodos.
En el paso 5, pA y pB apuntan exactamente al mismo nodo físico: ¡el nodo [100]!
Cero memoria auxiliar, O(N + M) tiempo lineal.

4. Implementación Canónica en Rust + Comparativa con Python#

Implementación en Rust (`practica-rust/dia_13.rs`)#

RUST

//! Implementación canónica de Intersección y Detección de Ciclos en Rust.
//! Compilable y verificable con `rustc --test`.

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ArenaNode {
    pub val: i32,
    pub next: Option<usize>,
}

#[derive(Debug, Default, Clone)]
pub struct ArenaList {
    pub nodes: Vec<ArenaNode>,
}

impl ArenaList {
    pub fn new() -> Self {
        Self::default()
    }

    pub fn add_node(&mut self, val: i32) -> usize {
        let idx = self.nodes.len();
        self.nodes.push(ArenaNode { val, next: None });
        idx
    }

    pub fn set_next(&mut self, from: usize, to: Option<usize>) {
        self.nodes[from].next = to;
    }

    /// CTCI 2.8 / LeetCode 141: Detección de ciclo con Tortuga y Liebre.
    pub fn has_cycle(&self, head: Option<usize>) -> bool {
        let mut slow = head;
        let mut fast = head;

        while let Some(fast_idx) = fast {
            if let Some(next_fast) = self.nodes[fast_idx].next {
                slow = self.nodes[slow.unwrap()].next;
                fast = self.nodes[next_fast].next;

                if slow.is_some() && slow == fast {
                    return true;
                }
            } else {
                break;
            }
        }

        false
    }

    /// CTCI 2.8 / LeetCode 142: Encuentra el índice exacto de inicio del ciclo en O(N) y O(1) espacio.
    pub fn find_cycle_start(&self, head: Option<usize>) -> Option<usize> {
        let mut slow = head;
        let mut fast = head;
        let mut has_intersection = false;

        // Fase 1: Detección de colisión
        while let Some(fast_idx) = fast {
            if let Some(next_fast) = self.nodes[fast_idx].next {
                slow = self.nodes[slow.unwrap()].next;
                fast = self.nodes[next_fast].next;

                if slow.is_some() && slow == fast {
                    has_intersection = true;
                    break;
                }
            } else {
                break;
            }
        }

        if !has_intersection {
            return None;
        }

        // Fase 2: Localización matemática de inicio
        let mut p1 = head;
        let mut p2 = slow;

        while p1 != p2 {
            p1 = self.nodes[p1.unwrap()].next;
            p2 = self.nodes[p2.unwrap()].next;
        }

        p1
    }

    /// CTCI 2.7 / LeetCode 160: Intersección mediante conmutación de punteros.
    pub fn find_intersection(&self, head_a: Option<usize>, head_b: Option<usize>) -> Option<usize> {
        if head_a.is_none() || head_b.is_none() {
            return None;
        }

        let mut p_a = head_a;
        let mut p_b = head_b;

        while p_a != p_b {
            p_a = match p_a {
                Some(idx) => self.nodes[idx].next,
                None => head_b,
            };
            p_b = match p_b {
                Some(idx) => self.nodes[idx].next,
                None => head_a,
            };
        }

        p_a
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_cycle_detection() {
        let mut arena = ArenaList::new();
        let n0 = arena.add_node(1);
        let n1 = arena.add_node(2);
        let n2 = arena.add_node(3);
        let n3 = arena.add_node(4);

        arena.set_next(n0, Some(n1));
        arena.set_next(n1, Some(n2));
        arena.set_next(n2, Some(n3));
        arena.set_next(n3, Some(n1)); // Ciclo hacia n1

        assert!(arena.has_cycle(Some(n0)));
        assert_eq!(arena.find_cycle_start(Some(n0)), Some(n1));
    }
}

Implementación Canónica en Python (`practica/dia_13_intersection_loop_detection.py`)#

PYTHON

def find_intersection_two_pointers(headA, headB):
    if not headA or not headB:
        return None
    pA, pB = headA, headB
    while pA != pB:
        pA = pA.next if pA else headB
        pB = pB.next if pB else headA
    return pA

def find_cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None

    p1, p2 = head, slow
    while p1 != p2:
        p1 = p1.next
        p2 = p2.next
    return p1

5. Las 3 Trampas Clásicas en Entrevistas#

Confundir Nodos con Valores Idénticos con Intersección: - Si lista_a = [1, 2, 3] y lista_b = [4, 2, 3], no intersectan a menos que los nodos [2] y [3] residan en la misma dirección de memoria física (id(a) == id(b) o *const T).
Ciclos Infinitos en Listas Disjuntas: - En la técnica de dos punteros para intersección, si las dos listas no intersectan, ambos punteros llegarán a None en la segunda pasada ( $p_A == None land p_B == None$ ). La condición p_a != p_b debe permitir que la igualdad None == None detenga el bucle.
Violación de Memoria en Avance Rápido: - Evaluar fast.next.next cuando fast.next es None provoca una excepción inmediata. La comprobación obligatoria antes de saltar es while fast.is_some() && fast.next.is_some().

6. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

Pregunta 1: ¿Por qué una lista enlazada en Rust implementada exclusivamente con Option<Box<ListNode>> no puede contener un ciclo cerrado de forma física?

Respuesta Técnica Detallada: Box<T> en Rust representa propiedad estricta y única (Unique Ownership). Si un nodo $A$ es dueño de $B$ a través de un Box, ningún otro nodo puede ser dueño de $B$ . Para que exista un ciclo, un nodo posterior $Z$ debería apuntar hacia $A$ . Pero $A$ ya es propiedad de su variable original o de su predecesor. Si $Z$ poseyera a $A$ mediante otro Box, $A$ tendría simultáneamente dos dueños independientes, lo cual está prohibido por las leyes fundamentales del sistema de tipos de Rust. Además, si un ciclo pudiera existir en Box, cuando la lista saliera de su ámbito, el destructor Drop entraría en un bucle infinito intentando liberar la memoria recursivamente. Por estas razones, en Rust los ciclos se modelan formalmente mediante índices de Arena (Vec<Node>) o tipos con conteo de referencias y mutabilidad interior (Rc<RefCell<Node>>).

Pregunta 2: ¿Por qué en el algoritmo de Floyd la Liebre no puede "saltar por encima" de la Tortuga dentro del ciclo sin llegar a coincidir en el mismo nodo?

Respuesta Técnica Detallada: Analicemos la distancia relativa $d$ entre la Liebre y la Tortuga medida en sentido del ciclo. En cada unidad de tiempo:

La Tortuga avanza $1$ posición.
La Liebre avanza $2$ posiciones.
El cambio en la distancia relativa es:

Δ d = (d + 1) - 2 = d - 1

En cada iteración individual, la distancia relativa disminuye estrictamente en exactamente 1 unidad. Como la distancia es un número entero no negativo ( $d \in ℕ$ ), una secuencia que disminuye de 1 en 1 ( $d, d-1, d-2, \dots$ ) está obligada por las propiedades de los números enteros a pasar por el valor $0$ antes de volverse negativa. Por lo tanto, es físicamente imposible que la Liebre salte por encima de la Tortuga sin coincidir exactamente en $d = 0$ (el mismo nodo).

Pregunta 3: ¿Cuál es la cota superior del número de pasos que realiza el algoritmo de Floyd antes de detectar una colisión?

Respuesta Técnica Detallada: Sean $k$ la longitud antes del ciclo y $C$ la longitud del ciclo:

La Tortuga tarda $k$ pasos en entrar al ciclo. Durante este tiempo, la Liebre da $2k$ pasos.
Una vez que la Tortuga entra al ciclo, la distancia máxima entre la Liebre y la Tortuga dentro del ciclo es $C - 1$ .
Como la distancia relativa disminuye en 1 en cada paso, tardarán como máximo $C - 1$ pasos adicionales en colisionar.

El número total de pasos antes de la colisión es estrictamente:

Pasos máximos \leq k + C = N

Por lo tanto, la fase 1 de Floyd se ejecuta en tiempo lineal $O(N)$ garantizado.

Pregunta 4: En el problema de intersección (LeetCode 160), ¿por qué la técnica de conmutación de punteros funciona con exactitud incluso cuando las dos listas tienen longitudes radicalmente diferentes?

Respuesta Técnica Detallada: Sean:

$a$ : Nodos exclusivos de la lista $A$ antes de la intersección.
$b$ : Nodos exclusivos de la lista $B$ antes de la intersección.
$c$ : Nodos compartidos en la cola común a partir de la intersección.

Longitud de $A$ : $L_A = a + c$ . Longitud de $B$ : $L_B = b + c$ .

Puntero $P_A$ : Recorre toda la lista $A$ ( $a + c$ pasos) y luego avanza por la lista $B$ hasta la intersección ( $b$ pasos). Pasos totales: $a + c + b$ .
Puntero $P_B$ : Recorre toda la lista $B$ ( $b + c$ pasos) y luego avanza por la lista $A$ hasta la intersección ( $a$ pasos). Pasos totales: $b + c + a$ .

Por la propiedad conmutativa de la adición matemática:

a + c + b = b + c + a

Ambos punteros caminan exactamente la misma cantidad de pasos y llegan al nodo de intersección en sincronía temporal perfecta.

Pregunta 5: Si te prohíben modificar las listas y te piden detectar si intersectan únicamente comprobando los últimos nodos, ¿cómo lo harías en tiempo

O(N + M)

y espacio

O(1)

Respuesta Técnica Detallada: Por la topología en forma de "Y", si dos listas intersectan, deben terminar obligatoriamente en el mismo nodo terminal (Tail).

Recorres la lista $A$ contando su longitud $L_A$ y guardando la dirección de su último nodo $Tail_A$ .
Recorres la lista $B$ contando su longitud $L_B$ y guardando su último nodo $Tail_B$ .
Si $Tail_A \neq Tail_B$ , las listas no intersectan (retornar None de inmediato).
Si $Tail_A == Tail_B$ , sabemos con certeza que intersectan. Calculamos la diferencia de longitud $d = |L_A - L_B|$ .
Avanzamos el puntero de la lista más larga $d$ pasos para alinearlos.
Avanzamos ambos punteros juntos hasta que coincidan: ese será el nodo de intersección.

7. Puente a LeetCode y Práctica de Código#

LeetCode 141 — Linked List Cycle (Easy): - Detección de ciclo con Tortuga y Liebre.
LeetCode 142 — Linked List Cycle II (Medium): - Localización del nodo exacto de inicio del ciclo.
LeetCode 160 — Intersection of Two Linked Lists (Easy): - Intersección de listas con conmutación de punteros.

Navegación:

← Volver a Sesión 12: Sum Lists y Palíndromos
Avanzar a Sesión 14: Consolidación y Simulacro Técnico de Semana 2 →