Sesión 11: Cracking the Coding Interview (Capítulo 2, Parte 2) — Eliminación de Nodos Intermedios y Partición de Listas#

Navegación rápida:

• ← Sesión 10: Runner Technique y Duplicados
• Sesión 12: Sum Lists y Palíndromos en Listas Enlazadas →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 50-65 minutos.
• Código fuente compilado y probado: practica-rust/dia_11.rs

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

Manipular listas enlazadas exige precisión quirúrgica: un puntero mal conectado provoca bucles infinitos en memoria o fugas de datos. Consulta el Glosario Maestro.

Eliminación por Sobreescritura (Copy & Bypass Trick)#

• (a) En palabras simples (intuición): Imagina que quieres que la persona #3 de una fila se vaya, pero no puedes avisarle a la persona #2 que la suelte. Entonces le dices a la persona #3: "copia la ropa y el nombre de la persona #4, y saca de la fila a la #4".
• (b) Definición técnica paso a paso: Estrategia para resolver CTCI 2.3 / LeetCode 237 cuando solo tenemos una referencia al nodo que deseamos eliminar. Como no podemos modificar el puntero next del nodo previo, copiamos el valor del nodo siguiente en el nodo actual (node.val = next_node.val) y luego desvinculamos el nodo siguiente (node.next = next_node.next).
• (c) Cómo funciona en Rust (memoria y tipos): Requiere una referencia mutable node: &mut ListNode. Si el nodo es el último de la lista (node.next.is_none()), no hay ningún nodo sucesor del cual copiar datos; por definición es matemáticamente irresoluble sin acceso al puntero previo o al head.
• (d) Error típico de Junior: Intentar aplicar este truco sobre el último nodo de la lista, intentando asignarle None a una referencia prestada, lo cual deja un nodo huérfano.

Partición Estable (Stable Partition)#

• (a) En palabras simples (intuición): En una fila mixta de niños y adultos, pides a todos los niños que pasen adelante y a todos los adultos que se queden atrás, pero cuidando rigurosamente que los niños mantengan entre sí el mismo orden en que llegaron.
• (b) Definición técnica paso a paso: Algoritmo que reorganiza una lista de modo que todos los nodos con valor menor a un pivote X aparezcan antes que los nodos con valor mayor o igual a X, preservando el orden relativo original de los elementos dentro de cada grupo.
• (c) Cómo funciona en Rust (memoria y tipos): Se crean dos listas independientes con nodos centinela en el Stack (smaller_dummy y greater_dummy). Conforme se itera la lista original, se desengancha cada nodo con take() y se inserta al final de la partición correspondiente en O(1).
• (d) Error típico de Junior: Olvidar limpiar el puntero next del último nodo de la partición de mayores (greater_tail.next = None), creando inadvertidamente un ciclo infinito en la lista enlazada final.

Reconexión de Listas (List Splicing)#

• (a) En palabras simples (intuición): Conectar dos mangueras de bomberos con un adaptador de rosca. La salida de la primera manguera se atornilla a la entrada de la segunda en un solo movimiento.
• (b) Definición técnica paso a paso: Operación en tiempo constante O(1) donde el puntero terminal de una lista (tail_a.next) se enlaza al primer nodo real de una segunda lista (dummy_b.next), fusionando ambas secuencias sin tener que recorrer los nodos intermedios.
• (c) Cómo funciona en Rust (memoria y tipos): Rust transfiere la posesión (Ownership) de la segunda sublista mediante asignación directa de punteros Box, sin duplicar memoria en el Heap.
• (d) Error típico de Junior: Perder la referencia a la cabeza de la lista resultante o conectar la cola apuntando al nodo centinela en lugar de al primer nodo con datos útiles.

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

El Dilema del Último Nodo en CTCI 2.3#

Pregunta clásica de Google y Microsoft: "Dada una lista enlazada y acceso ÚNICAMENTE a un nodo interno node, elimínalo en tiempo O(1)."

Analicemos qué significa "eliminar un nodo" en la memoria física:

1. Para que un nodo B deje de existir en la secuencia A → B → C, el puntero next del nodo anterior A debe modificarse para apuntar directamente a C (A → C).
2. Si no tenemos acceso a A (solo nos dieron un puntero a B): - No podemos viajar hacia atrás porque la lista es simplemente enlazada. - ¿Qué hacemos? Engañamos al sistema: - Leemos el valor de C: val_c = B.next.val. - Sobreescribimos el valor de B: B.val = val_c. - Saltamos a C: B.next = C.next. - Ahora el nodo B tiene el contenido de C, y el nodo C original queda liberado. La lista resultante es A → C_{copia} → D.

¿Por qué este truco es IMPOSIBLE si el nodo objetivo es el último (D → None)?#

Si el nodo es el último, no existe ningún nodo posterior del cual copiar un valor. No podemos "convertir a D en None" porque D es un bloque de memoria ya reservado en el Heap. La única forma de eliminar a D es que su predecesor apunte a None, lo cual es imposible sin acceso al predecesor. En una entrevista, debes señalar esta limitación de inmediato antes de escribir el código.

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

Flujo de Partición de Lista respecto a X#

Consulta el gráfico de arquitectura del sistema:

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

flowchart TD
    IN["Lista Original: [1] -> [4] -> [3] -> [2] -> [5], X = 3"] --> P{"¿node.val < X?"}
    P -->|val < 3| L["Agregar a lista 'Menores':<br/>smaller_tail.next = node"]
    P -->|val >= 3| G["Agregar a lista 'Mayores':<br/>greater_tail.next = node"]
    L --> JOIN["Concatenar en O(1):<br/>smaller_tail.next = greater_dummy.next"]
    G --> JOIN
    JOIN --> OUT["Resultado: [1] -> [2] -> [4] -> [3] -> [5]"]

Visualización Cuadro por Cuadro de Memoria: Partición Estable (X = 3)#

Entrada: 1 -> 4 -> 3 -> 2 -> 5 -> 2 -> None, X = 3.

INICIALIZACIÓN DE CENTINELAS:
smaller_dummy: [0] -> None (smaller_tail apunta aquí)
greater_dummy: [0] -> None (greater_tail apunta aquí)

PASO A PASO:
1. Nodo [1]: 1 < 3  -> smaller_tail.next = [1], smaller_tail = [1]
2. Nodo [4]: 4 >= 3 -> greater_tail.next = [4], greater_tail = [4]
3. Nodo [3]: 3 >= 3 -> greater_tail.next = [3], greater_tail = [3]
4. Nodo [2]: 2 < 3  -> smaller_tail.next = [2], smaller_tail = [2]
5. Nodo [5]: 5 >= 3 -> greater_tail.next = [5], greater_tail = [5]
6. Nodo [2]: 2 < 3  -> smaller_tail.next = [2], smaller_tail = [2]

ESTADO DE LAS SUB-LISTAS EN HEAP:
Menores: [0] -> [1] -> [2] -> [2] -> None
Mayores: [0] -> [4] -> [3] -> [5] -> None

RECONEXIÓN FINAL EN O(1):
1. smaller_tail.next = greater_dummy.next
   (El nodo [2] de Menores se conecta al nodo [4] de Mayores)
2. Retorno: smaller_dummy.next -> [1] -> [2] -> [2] -> [4] -> [3] -> [5] -> None.
Preserva el orden relativo original de forma perfecta y en O(1) memoria auxiliar.

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

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

//! Implementación canónica de Delete Middle y Partition 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.3: Elimina un nodo intermedio copiando datos del sucesor en O(1).
pub fn delete_middle_node(node: &mut ListNode) -> bool {
    if node.next.is_none() {
        return false;
    }

    let mut next_node = node.next.take().unwrap();
    node.val = next_node.val;
    node.next = next_node.next.take();
    true
}

/// CTCI 2.4 / LeetCode 86: Partición estable en O(N) tiempo y O(1) memoria auxiliar.
pub fn partition_stable(head: Option<Box<ListNode>>, x: i32) -> Option<Box<ListNode>> {
    let mut smaller_dummy = Box::new(ListNode::new(0));
    let mut greater_dummy = Box::new(ListNode::new(0));

    let mut smaller_tail = &mut smaller_dummy;
    let mut greater_tail = &mut greater_dummy;

    let mut curr = head;

    while let Some(mut node) = curr {
        let next = node.next.take();
        if node.val < x {
            smaller_tail.next = Some(node);
            smaller_tail = smaller_tail.next.as_mut().unwrap();
        } else {
            greater_tail.next = Some(node);
            greater_tail = greater_tail.next.as_mut().unwrap();
        }
        curr = next;
    }

    smaller_tail.next = greater_dummy.next;
    smaller_dummy.next
}

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

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

        // Eliminar nodo 2
        let node_2 = list.as_mut().unwrap().next.as_mut().unwrap();
        assert!(delete_middle_node(node_2));
        assert_eq!(list.as_ref().unwrap().next.as_ref().unwrap().val, 3);
    }
}

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

def delete_middle_node(node: ListNode) -> bool:
    if not node or not node.next:
        return False
    node.val = node.next.val
    node.next = node.next.next
    return True

def partition_stable(head: ListNode, x: int) -> ListNode:
    smaller_dummy = ListNode(0)
    greater_dummy = ListNode(0)
    smaller = smaller_dummy
    greater = greater_dummy

    curr = head
    while curr:
        if curr.val < x:
            smaller.next = curr
            smaller = smaller.next
        else:
            greater.next = curr
            greater = greater.next
        curr = curr.next

    greater.next = None  # Evita ciclos en memoria
    smaller.next = greater_dummy.next
    return smaller_dummy.next

5. Las 3 Trampas Clásicas en Entrevistas#

1. El Ciclo Infinito al No Limpiar el Último Nodo: - En Python, si el último nodo de la lista original era menor que X, el último nodo de la partición de mayores todavía apunta a él. Si no haces greater.next = None, crearás un ciclo cerrado infinito que congelará cualquier iteración posterior. En Rust, como desenganchamos con take(), este error se previene por diseño del sistema de tipos.
2. Confundir Partición Estable con Partición Inestable: - En CTCI 2.4 original, no se exige preservar el orden relativo (los menores pueden insertarse en cabeza invirtiendo su orden). Pero en LeetCode 86 se exige estabilidad estricta. Pregunta siempre qué comportamiento espera el entrevistador.
3. Intentar Modificar Nodos con Referencias Compartidas en Rust: - Para mutar la cola smaller_tail = smaller_tail.next.as_mut().unwrap(), la referencia debe ser exclusivamente mutable (&mut). El borrow checker asegura que solo un puntero tenga control sobre la cola en cada paso.

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

node.next = head_part;
head_part = Some(node);

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

1. LeetCode 237 — Delete Node in a Linked List (Medium): - Implementa el truco de copia y bypass in-place.
2. LeetCode 86 — Partition List (Medium): - Implementa la partición estable con dos nodos ficticios centinela.
3. LeetCode 328 — Odd Even Linked List (Medium): - Agrupa los nodos por índices pares e impares aplicando la misma técnica de reconexión de listas.

Navegación:

• ← Volver a Sesión 10: Runner Technique y Duplicados
• Avanzar a Sesión 12: Sum Lists y Palíndromos en Listas Enlazadas →