Lumænaut_

Declaración del Problema

Se te proporcionan dos listas enlazadas no vacías que representan dos enteros no negativos. Los dígitos están almacenados en orden inverso, y cada nodo contiene un solo dígito. Suma los dos números y devuelve la suma como una lista enlazada.

Puedes asumir que los dos números no contienen ningún cero a la izquierda, excepto el propio número 0.

Entrada: l1 = [2,4,3], l2 = [5,6,4]
Salida: [7,0,8]
Explicación: 342 + 465 = 807.

Entrada: l1 = [0], l2 = [0]
Salida: [0]

Entrada: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Salida: [8,9,9,9,0,0,0,1]
          

Restricciones:

• El número de nodos en cada lista enlazada está en el rango [1, 100].
• 0 <= Nodo.val <= 9
• Se garantiza que la lista representa un número que no tiene ceros a la izquierda.

Reescribiendo en Términos Simples

Imagina que tienes dos números escritos al revés. Por ejemplo, 342 se almacena como 2 → 4 → 3. Se te pide sumarlos dígito por dígito de izquierda a derecha, tal como lo hacíamos en la primaria, pero con las listas invertidas. ¿El truco? El resultado también debe ser una lista enlazada invertida. Así que, en lugar de lidiar con enteros grandes, simulamos la suma manual con un acarreo. Eso es todo — excepto que debemos hacerlo eficientemente mientras recorremos dos listas enlazadas que pueden tener longitudes diferentes.

Camino hacia lo Óptimo: De lo Ingenuo a lo Magistral

Paso 1 – El Enfoque Ingenuo: Convertir a Números

La idea más directa: recorrer cada lista enlazada, construir el entero real (invirtiendo el orden de los dígitos), sumarlos y luego convertir la suma de nuevo a una lista enlazada invertida. En Python podría verse así:

def obtener_numero(cabeza):
    num = 0
    lugar = 1
    while cabeza:
        num += cabeza.val * lugar
        lugar *= 10
        cabeza = cabeza.next
    return num
# Luego hacer la suma y reconstruir
          

Esto funciona, pero tiene un problema fatal cuando los números exceden los enteros de 64 bits. Dado que cada lista enlazada puede tener hasta 100 dígitos, el entero puede ser tan grande como 10¹⁰⁰ — los enteros grandes de Python pueden manejarlo, pero en lenguajes como C++ o Java, habría desbordamiento. Además, el problema pretende explícitamente entrenarnos en el recorrido de listas enlazadas y la gestión del acarreo, no en bibliotecas de números grandes. Así que este método ingenuo es ineficiente conceptualmente.

Paso 2 – Simulación con Acarreo (El Enfoque Estándar)

La idea clave: la suma se realiza dígito por dígito desde el dígito menos significativo (que es la cabeza de la lista, gracias al orden inverso). Así que recorremos ambas listas simultáneamente, sumamos los dígitos actuales más un acarreo, almacenamos el dígito (suma % 10) en un nuevo nodo y propagamos el acarreo (suma // 10). Continuamos hasta que ambas listas se agoten y el acarreo sea 0.

Este algoritmo se ejecuta en O(max(m, n)) tiempo, donde m y n son las longitudes de las listas, y O(max(m, n)) espacio para la lista resultado (si ignoramos la salida, es óptimo). La clave es el truco del nodo ficticio que simplifica los casos extremos — nunca tienes que tratar el primer nodo de manera especial.

Paso 3 – Optimizando Memoria y Casos Extremos

¿Podríamos evitar crear una nueva lista? En teoría, podríamos reutilizar una de las listas de entrada para almacenar el resultado, modificando los nodos en su lugar. Esto reduciría la complejidad espacial a O(1) además de la respuesta. Sin embargo, es complicado porque podríamos necesitar extender una lista si el acarreo final agrega un nuevo nodo. Por lo general, los entrevistadores y LeetCode aceptan la construcción de una nueva lista porque es más limpia. La verdadera optimización es reconocer que debemos manejar el acarreo final por separado.

Formulación Matemática

Soluciones en Múltiples Lenguajes

A continuación encontrarás implementaciones limpias del algoritmo óptimo en seis lenguajes. Cada una usa el patrón del nodo ficticio y se ejecuta en O(n) tiempo.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        current = 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
            current.next = ListNode(total % 10)
            current = current.next

            if l1: l1 = l1.next
            if l2: l2 = l2.next

        return dummy.next
              

/**
* Definition for singly-linked list.
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
var addTwoNumbers = function(l1, l2) {
    let dummy = new ListNode(0);
    let current = dummy;
    let carry = 0;

    while (l1 !== null || l2 !== null || carry !== 0) {
        const val1 = l1 ? l1.val : 0;
        const val2 = l2 ? l2.val : 0;
        const sum = val1 + val2 + carry;
        carry = Math.floor(sum / 10);
        current.next = new ListNode(sum % 10);
        current = current.next;

        if (l1) l1 = l1.next;
        if (l2) l2 = l2.next;
    }

    return dummy.next;
};  
              

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        ListNode* current = dummy;
        int carry = 0;

        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            int val1 = (l1 != nullptr) ? l1->val : 0;
            int val2 = (l2 != nullptr) ? l2->val : 0;
            int sum = val1 + val2 + carry;
            carry = sum / 10;
            current->next = new ListNode(sum % 10);
            current = current->next;

            if (l1 != nullptr) l1 = l1->next;
            if (l2 != nullptr) l2 = l2->next;
        }

        ListNode* result = dummy->next;
        delete dummy;
        return result;
    }
};
        

/**
* Definition for singly-linked list.
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{0, nil}
    current := dummy
    carry := 0

    for l1 != nil || l2 != nil || carry != 0 {
        val1, val2 := 0, 0
        if l1 != nil {
            val1 = l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            val2 = l2.Val
            l2 = l2.Next
        }
        sum := val1 + val2 + carry
        carry = sum / 10
        current.Next = &ListNode{sum % 10, nil}
        current = current.Next
    }
    return dummy.Next
}
              

/**
* Example:
* var li = ListNode(5)
* var v = li.`val`
* Definition for singly-linked list.
* class ListNode(var `val`: Int) {
*     var next: ListNode? = null
* }
*/
class Solution {
    fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
        val dummy = ListNode(0)
        var current: ListNode? = dummy
        var carry = 0
        var p = l1
        var q = l2

        while (p != null || q != null || carry != 0) {
            val x = p?.`val` ?: 0
            val y = q?.`val` ?: 0
            val sum = x + y + carry
            carry = sum / 10
            current?.next = ListNode(sum % 10)
            current = current?.next

            if (p != null) p = p.next
            if (q != null) q = q.next
        }

        return dummy.next
    }
}
              

/**
* Definition for singly-linked list.
* public class ListNode {
*     public var val: Int
*     public var next: ListNode?
*     public init() { self.val = 0; self.next = nil; }
*     public init(_ val: Int) { self.val = val; self.next = nil; }
*     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        let dummy = ListNode(0)
        var current: ListNode? = dummy
        var carry = 0
        var p = l1
        var q = l2

        while p != nil || q != nil || carry != 0 {
            let x = p?.val ?? 0
            let y = q?.val ?? 0
            let sum = x + y + carry
            carry = sum / 10
            current?.next = ListNode(sum % 10)
            current = current?.next

            p = p?.next
            q = q?.next
        }

        return dummy.next
    }
}
              

Casos Extremos y Trampas

• Longitudes de lista diferentes: El algoritmo maneja esto elegantemente asignando 0 a los nodos faltantes.
• Acarreo final: ej., 999 + 1 = 1000 → lista de salida [0,0,0,1]. Nuestra condición de bucle incluye carry != 0 para agregar ese nodo extra.
• Una lista vacía (aunque el problema dice no vacías, pero en seguimientos): Simplemente devuelve la otra lista con la posible adición de acarreo.
• Números grandes: La solución funciona para números de 100 dígitos porque nunca los convierte a enteros — solo trabaja con dígitos y acarreo.

Análisis de Complejidad

Complejidad de Tiempo: O(max(m, n)) donde m, n son las longitudes de l1 y l2. Recorremos cada nodo como máximo una vez.

Complejidad de Espacio: O(max(m, n)) para la nueva lista. Si ignoramos la salida, es O(1) de espacio auxiliar (solo unas pocas variables). Algunas soluciones reutilizan una de las listas de entrada para lograr O(1) de espacio extra, pero a costa de mutar las entradas — es un compromiso.

Lecciones Aprendidas y Aplicaciones Prácticas

El problema “Suma de Dos Números” es un microcosmos de cómo funciona la aritmética de bajo nivel en todo sistema digital. El algoritmo de propagación de acarreo que implementas aquí es el mismo bloque fundamental utilizado en bibliotecas aritméticas de precisión arbitraria, módulos criptográficos e incluso ALUs de hardware. Al dominar este patrón, obtienes una visión de cómo el software maneja números más allá de los tamaños de palabra nativos de la máquina.

Más allá de las entrevistas, esta técnica aparece en escenarios del mundo real: implementar aritmética de enteros grandes en contratos inteligentes de blockchain donde los costos de gas exigen operaciones dígito por dígito eficientes, construir software financiero de alto rendimiento que requiere aritmética decimal exacta, u optimizar sistemas embebidos donde la memoria es limitada. El patrón del nodo ficticio también enseña una estrategia reutilizable para la construcción de listas enlazadas — un patrón que se aplica para fusionar listas ordenadas, particionar listas y más.

Referencias y Recursos Adicionales

• Problema Original en LeetCode
• Wikipedia – Aritmética elemental (suma)
• Acarreo (aritmética) – el mecanismo que lo hace funcionar
• GMP – Biblioteca Aritmética de Múltiple Precisión GNU
• TheAlgorithms – implementaciones de código abierto en muchos lenguajes
• GeeksforGeeks: Suma dos números representados por listas enlazadas