Sesión 14: Consolidación de Semana 2 y Gran Simulacro Técnico de Listas Enlazadas#

Navegación rápida:

• ← Sesión 13: Intersección y Detección de Ciclos
• Sesión 15: Divide y Vencerás y Quicksort (Grokking Ch 4) →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 60-80 minutos.
• Código fuente compilado y probado: practica-rust/dia_14.rs

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

Cerramos la Semana 2 consolidando los 5 patrones arquitectónicos que resuelven el 95% de los problemas de listas enlazadas en entrevistas técnicas. Consulta el Glosario Maestro.

Intercalado de Nodos (List Weaving / Interleaving)#

• (a) En palabras simples (intuición): Mezclar dos barajas de cartas como un crupier de casino: una carta de la izquierda, una de la derecha, una de la izquierda, una de la derecha, hasta combinarlas en un solo mazo.
• (b) Definición técnica paso a paso: Operación donde dos listas enlazadas independientes L₁ y L₂ se combinan alternando sus nodos consecutivamente: L₁[0] → L₂[0] → L₁[1] → L₂[1] …. Se ejecuta en tiempo O(N) y espacio O(1) reconfigurando exclusivamente los punteros next.
• (c) Cómo funciona en Rust (memoria y tipos): Manipula la propiedad mediante take(): se resguarda temporalmente el siguiente nodo de L₁, se injerta el nodo de L₂, y luego se restablece el enlace, preservando la exclusividad mutable sin clonar nodos.
• (d) Error típico de Junior: Perder el puntero de continuación de L₁ al sobreescribir p1.next = p2, dejando huérfano el resto de la primera lista.

Los 5 Patrones Maestros de Listas Enlazadas#

• (a) En palabras simples (intuición): Las cinco herramientas maestras en tu caja de carpintería: el martillo (centinela), el metro (corredor), el destornillador (inversor), el pegamento (fusión) y el radar (Floyd).
• (b) Definición técnica paso a paso:

1. Nodo Centinela (Dummy Node): Elimina condiciones especiales para el head.
2. Corredores Rápido y Lento (Fast/Slow): Localiza el centro exacto o el elemento a distancia k.
3. Inversión In-Place de 3 Punteros (prev, curr, next): Invierte enlaces en O(1) memoria.
4. Fusión de Listas Ordenadas (Merge Two Lists): Intercala secuencias respetando el orden.
5. Detección de Ciclos de Floyd (Tortoise and Hare): Detecta bucles en O(1) espacio.

• (c) Cómo funciona en Rust (memoria y tipos): Todos estos patrones se ejecutan en O(1) memoria auxiliar en el Heap y O(1) marcos en el Stack cuando se implementan de forma iterativa.
• (d) Error típico de Junior: Intentar resolver problemas complejos de listas como Reorder List (LeetCode 143) de un solo golpe con bucles anidados en lugar de descomponerlo en 3 fases primitivas.

Complejidad Compuesta en Algoritmos Multifase#

• (a) En palabras simples (intuición): Lavar tu ropa toma 30 minutos, secarla toma 30 minutos y doblarla toma 15 minutos. El tiempo total es la suma de los tres pasos (75 minutos), no la multiplicación.
• (b) Definición técnica paso a paso: Cuando un algoritmo ejecuta secuencialmente varias fases donde cada fase toma tiempo lineal O(N), el costo asintótico total se suma:

• (c) Cómo funciona en Rust (memoria y tipos): Mantener cada fase en O(1) espacio auxiliar garantiza que la memoria total del sistema permanezca en O(1) de principio a fin.
• (d) Error típico de Junior: Temer dividir un algoritmo en 3 pasadas independientes y preferir un código enredado y lleno de bugs en una sola pasada bajo la falsa creencia de que 3 pasadas son "más lentas en Big O".

2. Desglose Conceptual desde Primeros Principios: Anatomía de LeetCode 143 (Reorder List)#

Problema: Dada una lista enlazada L₀ → L₁ → … → L_{n-1} → Lₙ, reordénala in-place como:

¿Por Qué la Fuerza Bruta Fracasa?#

En una lista simplemente enlazada, para traer el último nodo Lₙ al frente después de L₀, debemos recorrer N nodos. Para traer el siguiente último L_{n-1}, debemos recorrer N-1 nodos.

La Solución de Nivel Staff en 3 Fases (O(N) Tiempo, O(1) Espacio)#

Descomponemos el problema en tres operaciones que dominamos:

FASE 1: Dividir la lista en dos mitades (Corredor Rápido y Lento)
Entrada: [1] -> [2] -> [3] -> [4] -> [5] -> [6]
Mitad 1: [1] -> [2] -> [3] -> None
Mitad 2: [4] -> [5] -> [6] -> None
Costo: O(N) tiempo, O(1) espacio.

FASE 2: Invertir la segunda mitad in-place
Mitad 2 invertida: [6] -> [5] -> [4] -> None
Costo: O(N) tiempo, O(1) espacio.

FASE 3: Intercalar ambas mitades nodo por nodo
Puntero 1 en [1], Puntero 2 en [6]:
- [1] apunta a [6]
- [6] apunta a [2]
- [2] apunta a [5]
- [5] apunta a [3]
- [3] apunta a [4] -> None
Resultado: [1] -> [6] -> [2] -> [5] -> [3] -> [4] -> None.
Costo: O(N) tiempo, O(1) espacio.

¡Costo total agregado: O(N) tiempo lineal y O(1) memoria auxiliar!

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

Diagrama de los 5 Patrones Maestros#

Consulta la visualización general de la arquitectura:

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

flowchart TD
    P1["1. Dummy Node (Evita edge cases en head)"]
    P2["2. Runner Fast/Slow (Mitad y ciclos)"]
    P3["3. Reverse In-Place (Inversión con 3 punteros)"]
    P4["4. Merge Two Sorted Lists (Fusión ordenada O(N+M))"]
    P5["5. Floyd Detection (Colisión Liebre y Tortuga)"]

Visualización Cuadro por Cuadro de Memoria: Reorder List (N = 4)#

Entrada: [1] -> [2] -> [3] -> [4] -> None

PASO 1: PARTIR A LA MITAD
half = 2. first_tail se detiene en [2].
first_tail.next.take() desconecta la segunda mitad.
L1: [1] -> [2] -> None
L2: [3] -> [4] -> None

PASO 2: INVERTIR SEGUNDA MITAD
reverse_list(L2) -> [4] -> [3] -> None

PASO 3: INTERCALADO PASO A PASO
p1 está en [1], second_reversed está en [4].

Iteración 1:
- second_node = [4] (extraído con take)
- p1_next = [2]
- second_node.next = [2] -> [4] -> [2]
- p1.next = Some([4])   -> [1] -> [4] -> [2]
- p1 avanza a [2]

Iteración 2:
- second_node = [3]
- p1_next = None
- second_node.next = None -> [3] -> None
- p1.next = Some([3])     -> [1] -> [4] -> [2] -> [3] -> None

Resultado final: [1] -> [4] -> [2] -> [3] -> None.

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

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

//! Implementación canónica de consolidación y simulacro en Rust.
//! Compilable y verificable con `rustc --test`.

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

impl ListNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}

/// LeetCode 876: Encuentra el nodo central de la lista.
pub fn get_middle_node(head: &Option<Box<ListNode>>) -> Option<&ListNode> {
    let mut slow = head.as_deref();
    let mut fast = head.as_deref();

    while let Some(fast_node) = fast {
        if let Some(next_fast) = fast_node.next.as_deref() {
            slow = slow.unwrap().next.as_deref();
            fast = next_fast.next.as_deref();
        } else {
            break;
        }
    }

    slow
}

/// LeetCode 21: Fusión de dos listas ordenadas en O(N + M) tiempo y O(1) espacio.
pub fn merge_two_sorted_lists(
    mut l1: Option<Box<ListNode>>,
    mut l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    let mut dummy = Box::new(ListNode::new(0));
    let mut tail = &mut dummy;

    while l1.is_some() && l2.is_some() {
        if l1.as_ref().unwrap().val <= l2.as_ref().unwrap().val {
            let next = l1.as_mut().unwrap().next.take();
            tail.next = l1;
            l1 = next;
        } else {
            let next = l2.as_mut().unwrap().next.take();
            tail.next = l2;
            l2 = next;
        }
        tail = tail.next.as_mut().unwrap();
    }

    tail.next = if l1.is_some() { l1 } else { l2 };
    dummy.next
}

/// Invierte una lista enlazada in-place en O(1) espacio.
pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut prev = None;
    let mut curr = head;
    while let Some(mut node) = curr {
        let next = node.next.take();
        node.next = prev;
        prev = Some(node);
        curr = next;
    }
    prev
}

/// LeetCode 143: Reorder List en 3 fases continuas O(N) tiempo y O(1) espacio.
pub fn reorder_list(head: &mut Option<Box<ListNode>>) {
    if head.is_none() || head.as_ref().unwrap().next.is_none() {
        return;
    }

    // 1. Contar longitud para partir
    let mut len = 0;
    let mut curr = head.as_ref();
    while let Some(node) = curr {
        len += 1;
        curr = node.next.as_ref();
    }

    let half = (len + 1) / 2;
    let mut first_tail = head.as_mut().unwrap();
    for _ in 1..half {
        first_tail = first_tail.next.as_mut().unwrap();
    }

    // Desconectar segunda mitad
    let second_half = first_tail.next.take();

    // 2. Invertir la segunda mitad
    let mut second_reversed = reverse_list(second_half);

    // 3. Intercalar ambas mitades
    let mut p1 = head.as_mut().unwrap();

    while second_reversed.is_some() {
        let mut second_node = second_reversed.unwrap();
        second_reversed = second_node.next.take();

        let p1_next = p1.next.take();
        second_node.next = p1_next;
        p1.next = Some(second_node);

        if p1.next.as_ref().unwrap().next.is_some() {
            p1 = p1.next.as_mut().unwrap().next.as_mut().unwrap();
        } else {
            break;
        }
    }
}

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

    #[test]
    fn test_merge_sorted() {
        let mut l1 = Some(Box::new(ListNode::new(1)));
        l1.as_mut().unwrap().next = Some(Box::new(ListNode::new(3)));

        let mut l2 = Some(Box::new(ListNode::new(2)));
        l2.as_mut().unwrap().next = Some(Box::new(ListNode::new(4)));

        let merged = merge_two_sorted_lists(l1, l2);
        assert_eq!(merged.as_ref().unwrap().val, 1);
        assert_eq!(merged.as_ref().unwrap().next.as_ref().unwrap().val, 2);
    }
}

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

def reorder_list(head):
    if not head or not head.next:
        return
    # 1. Encontrar la mitad
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # 2. Invertir segunda mitad
    prev, curr = None, slow.next
    slow.next = None  # Desconectar mitades
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt

    # 3. Intercalar
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first, second = tmp1, tmp2

5. Las 3 Trampas Clásicas en Entrevistas#

1. No Desconectar la Primera Mitad de la Segunda Mitad: - En Reorder List, si olvidas hacer first_tail.next = None (o take()), el último nodo de la primera mitad continuará apuntando al inicio original de la segunda mitad. Cuando comiences a intercalar, se formará un ciclo cerrado que provocará un bucle infinito en las pruebas automáticas.
2. Listas de Longitud Impar vs Par: - Al partir la lista a la mitad, la primera mitad debe contener ⌈ N / 2 ⌉ elementos (es decir, el elemento central impar debe pertenecer a la primera mitad). Si dejas el central en la segunda mitad, el intercalado quedará desfasado.
3. El Error de Clonación en Fusiones: - En merge_two_sorted_lists, muchos candidatos novatos crean nodos completamente nuevos con Box::new(). Un entrevistador senior exigirá una solución in-place que reutilice los nodos existentes mediante reasignación de punteros.

6. Preguntas de Comprensión Profunda y Diagnóstico Socrático (Gran Examen de Semana 2)#

7. Puente a LeetCode y Gran Simulacro Técnico de Semana 2#

Prueba tus habilidades de certificación de Semana 2 resolviendo los siguientes problemas bajo cronómetro (45 minutos en total para los tres):

1. LeetCode 876 — Middle of the Linked List (Easy): - Corredor 2x vs 1x.
2. LeetCode 21 — Merge Two Sorted Lists (Easy): - Fusión in-place con Dummy Node.
3. LeetCode 143 — Reorder List (Medium): - El gran reto compuesto: Mitad + Inversión + Intercalado in-place.

Navegación:

• ← Volver a Sesión 13: Intersección y Detección de Ciclos
• Avanzar a Sesión 15: Divide y Vencerás y Quicksort (Semana 3) →