Sesión 12: Cracking the Coding Interview (Capítulo 2, Parte 3) — Sum Lists y Palíndromos en Listas Enlazadas#

Navegación rápida:

• ← Sesión 11: Delete Middle Node y Partition
• Sesión 13: Intersección y Detección de Ciclos en Listas Enlazadas →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 55-70 minutos.
• Código fuente compilado y probado: practica-rust/dia_12.rs

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

La aritmética de precisión arbitraria y la verificación de simetría en estructuras enlazadas son dos de los problemas más frecuentes en pruebas técnicas. Consulta el Glosario Maestro.

Acarreo Aritmético (Carry Propagation)#

• (a) En palabras simples (intuición): Cuando sumas 7 + 5 = 12 en un papel con lápiz, escribes el $2$ abajo y te "llevas $1$" a la siguiente columna a la izquierda.
• (b) Definición técnica paso a paso: En aritmética posicional de base B=10, la suma de dos dígitos más el acarreo entrante genera una suma total S ∈ [0, 19]. El nuevo dígito que se almacena en el nodo actual es S ±od{10} y el nuevo acarreo para el siguiente nodo es ⌊ S / 10 ⌋.
• (c) Cómo funciona en Rust (memoria y tipos): El bucle principal debe mantenerse activo mientras l1.is_some() || l2.is_some() || carry != 0. Si al terminar ambas listas carry == 1, se crea un último nodo adicional para alojar el dígito más significativo.
• (d) Error típico de Junior: Olvidar la condición carry != 0 en el bucle, haciendo que 99 + 1 devuelva erróneamente $00$ en lugar de $100$.

Orden Inverso (Little-Endian) vs Orden Directo (Big-Endian)#

• (a) En palabras simples (intuición): Little-Endian es leer el número al revés empezando por las unidades (ej. $617$ se guarda como 7 → 1 → 6). Big-Endian es leerlo normal de izquierda a derecha (6 → 1 → 7).
• (b) Definición técnica paso a paso: En la variante inversa (Reverse Order), las cabezas de las dos listas coinciden con el dígito menos significativo (10⁰), permitiendo sumar y propagar el acarreo hacia adelante de forma natural en una sola pasada O(N). En la variante directa (Forward Order), las cabezas corresponden al dígito más significativo (10^{N-1}), lo que obliga a igualar longitudes rellenando con ceros a la izquierda o invertir el flujo usando una Pila LIFO.
• (c) Cómo funciona en Rust (memoria y tipos): Para el orden directo, apilar los dígitos en dos vectores Vec<i32> en el Stack/Heap permite extraerlos de derecha a izquierda con pop() en tiempo O(1).
• (d) Error típico de Junior: Intentar convertir la lista enlazada a un entero nativo primitivo (u64), lo cual falla por desbordamiento numérico cuando la lista representa un número de 100 dígitos.

Detección de Punto Medio con Corredor 2x vs 1x#

• (a) En palabras simples (intuición): Dos corredores salen del mismo punto. La Liebre corre al doble de velocidad que la Tortuga. Cuando la Liebre cruza la línea de meta al final de la pista, la Tortuga está parada exactamente en la mitad de la pista.
• (b) Definición técnica paso a paso: Técnica de dos punteros donde fast avanza 2 nodos por iteración (fast = fast.next.next) y slow avanza 1 nodo (slow = slow.next). Al terminar la lista, slow queda ubicado en el nodo central.
• (c) Cómo funciona en Rust (memoria y tipos): Permite implementar la verificación de palíndromos apilando los elementos de la primera mitad en una Pila conforme slow avanza. Si la lista tiene longitud impar, fast no será None, lo que indica que slow debe saltar el nodo central antes de comparar.
• (d) Error típico de Junior: Desreferenciar fast.next.next sin verificar si fast o fast.next son nulos, causando pánicos por puntero nulo.

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

La Matemática de la Suma de Listas (Little-Endian)#

Sean dos números A y B:

En la lista enlazada en orden inverso, el nodo en la posición k contiene exactamente el coeficiente de 10ᵏ. El algoritmo suma los coeficientes de igual potencia:

Donde:

• c_{-1} = 0 (acarreo inicial).
• dₖ = Sₖ ±od{10} (dígito guardado en el nuevo nodo).
• cₖ = ⌊ Sₖ / 10 ⌋ (acarreo propagado al siguiente término).

Como las dos listas pueden tener longitudes distintas (N ≠ M), si una lista se agota antes que la otra, su dígito faltante se asume como $0$. El número máximo de nodos en la lista resultante es max(N, M) + 1:

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

Flujo de Suma Dígito a Dígito con Acarreo#

Consulta el gráfico vectorial de arquitectura:

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

flowchart LR
    L1["L1: [7] -> [1] -> [6] (617)"]
    L2["L2: [5] -> [9] -> [2] (295)"]
    L1 & L2 --> SUM["Suma dígito a dígito + Carry:<br/>7+5=12 -> [2], carry=1<br/>1+9+1=11 -> [1], carry=1<br/>6+2+1=9 -> [9], carry=0"]
    SUM --> RES["Resultado: [2] -> [1] -> [9] (912)"]

Visualización Cuadro por Cuadro de Memoria: Sum Lists (617 + 295 = 912)#

Entradas en Heap: L₁: [7] -> [1] -> [6] L₂: [5] -> [9] -> [2]

ESTADO INICIAL:
carry = 0
dummy: [0] -> None (tail apunta a dummy)

ITERACIÓN 1:
- sum = 0 + L1(7) + L2(5) = 12
- digit = 12 % 10 = 2
- carry = 12 / 10 = 1
- tail.next = [2]
- tail avanza a [2]
Resultado: [0] -> [2]

ITERACIÓN 2:
- sum = 1 (carry) + L1(1) + L2(9) = 11
- digit = 11 % 10 = 1
- carry = 11 / 10 = 1
- tail.next = [1]
- tail avanza a [1]
Resultado: [0] -> [2] -> [1]

ITERACIÓN 3:
- sum = 1 (carry) + L1(6) + L2(2) = 9
- digit = 9 % 10 = 9
- carry = 9 / 10 = 0
- tail.next = [9]
- tail avanza a [9]
Resultado: [0] -> [2] -> [1] -> [9]

FIN: l1 es None, l2 es None, carry es 0.
dummy.next retorna: [2] -> [1] -> [9] (representa 912).

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

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

//! Implementación canónica de Sum Lists y Palíndromos 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 }
    }
}

/// CTCI 2.5 / LeetCode 2: Suma de listas en orden inverso O(max(N, M)).
pub fn sum_lists_reverse(
    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;
    let mut carry = 0;

    while l1.is_some() || l2.is_some() || carry != 0 {
        let mut sum = carry;

        if let Some(node) = l1 {
            sum += node.val;
            l1 = node.next;
        }

        if let Some(node) = l2 {
            sum += node.val;
            l2 = node.next;
        }

        carry = sum / 10;
        let digit = sum % 10;

        tail.next = Some(Box::new(ListNode::new(digit)));
        tail = tail.next.as_mut().unwrap();
    }

    dummy.next
}

/// CTCI 2.5 (Forward Order): Suma de listas en orden directo utilizando dos pilas auxiliares.
pub fn sum_lists_forward(
    l1: &Option<Box<ListNode>>,
    l2: &Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    let mut s1 = Vec::new();
    let mut s2 = Vec::new();

    let mut curr = l1;
    while let Some(node) = curr {
        s1.push(node.val);
        curr = &node.next;
    }

    let mut curr2 = l2;
    while let Some(node) = curr2 {
        s2.push(node.val);
        curr2 = &node.next;
    }

    let mut head = None;
    let mut carry = 0;

    while !s1.is_empty() || !s2.is_empty() || carry != 0 {
        let mut sum = carry;
        if let Some(v) = s1.pop() {
            sum += v;
        }
        if let Some(v) = s2.pop() {
            sum += v;
        }

        carry = sum / 10;
        let digit = sum % 10;

        let mut new_node = Box::new(ListNode::new(digit));
        new_node.next = head;
        head = Some(new_node);
    }

    head
}

/// CTCI 2.6 / LeetCode 234: Verifica si una lista es palíndromo con una Pila auxiliar y corredor 2x/1x.
pub fn is_palindrome_stack(head: &Option<Box<ListNode>>) -> bool {
    let mut stack = Vec::new();
    let mut slow = head;
    let mut fast = head;

    while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
        stack.push(slow.as_ref().unwrap().val);
        slow = &slow.as_ref().unwrap().next;
        fast = &fast.as_ref().unwrap().next.as_ref().unwrap().next;
    }

    if fast.is_some() {
        slow = &slow.as_ref().unwrap().next; // Salta el nodo central en listas impares
    }

    while let Some(node) = slow {
        if let Some(top_val) = stack.pop() {
            if node.val != top_val {
                return false;
            }
        } else {
            return false;
        }
        slow = &node.next;
    }

    true
}

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

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

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

        let res = sum_lists_reverse(l1, l2);
        assert_eq!(res.as_ref().unwrap().val, 2);
        assert_eq!(res.as_ref().unwrap().next.as_ref().unwrap().val, 1);
        assert_eq!(res.as_ref().unwrap().next.as_ref().unwrap().next.as_ref().unwrap().val, 9);
    }
}

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

def sum_lists_reverse(l1, l2):
    dummy = ListNode(0)
    tail = dummy
    carry = 0
    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0
        total = val1 + val2 + carry
        carry = total // 10
        tail.next = ListNode(total % 10)
        tail = tail.next
        if l1: l1 = l1.next
        if l2: l2 = l2.next
    return dummy.next

5. Las 3 Trampas Clásicas en Entrevistas#

1. El Acarreo Final: - Para 99 + 1 = 100, ambas listas terminan tras dos iteraciones, pero queda un carry = 1. La condición while l1 || l2 || carry != 0 garantiza crear el último nodo [1].
2. El Elemento Central en Palíndromos de Longitud Impar: - En una lista impar como 1 -> 2 -> 3 -> 2 -> 1, el número 3 es el centro. No tiene pareja con la cual compararse. Si no avanzas slow = slow.next cuando fast.is_some(), la comparación con la pila fallará.
3. Desbordamiento de Enteros Primitivos: - Nunca intentes resolver Sum Lists convirtiendo las listas en enteros estándar de 64 bits (l1_val + l2_val). Si el número tiene 100 dígitos, se desbordará. Debes operar dígito a dígito en los nodos.

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

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

1. LeetCode 2 — Add Two Numbers (Medium): - Implementa sum_lists_reverse con acarreo.
2. LeetCode 445 — Add Two Numbers II (Medium): - Resuelve la variante en orden directo (Forward Order) con pilas.
3. LeetCode 234 — Palindrome Linked List (Easy): - Resuelve primero con Pila y luego in-place invirtiendo la segunda mitad en O(1) espacio.

Navegación:

• ← Volver a Sesión 11: Delete Middle Node y Partition
• Avanzar a Sesión 13: Intersección y Detección de Ciclos en Listas Enlazadas →