lumænaut

Soluciones LeetCode
#2 — Suma dos números

De la suma de primaria al dominio de listas ligadas

Por Alberto Del Valle

(Tiempo de lectura ~4 min)

Arte ASCII a color: una computadora anticuada sobre un escritorio con una estantería al fondo, que sugiere un espacio de trabajo clásico para programar.

Enunciado del problema

Se te dan dos listas ligadas 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 ligada.

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

Ejemplo 1:

Ejemplo 2:

Ejemplo 3:

Restricciones:

  • El número de nodos en cada lista ligada está en el rango [1, 100].

  • 0 <= Node.val <= 9

  • Se garantiza que la lista representa un número que no tiene ceros a la izquierda.

El enfoque ingenuo

La idea más directa: recorrer cada lista, reconstruir el entero (multiplicando por potencias de 10 según avanzamos), sumarlos y luego construir una nueva lista ligada en orden inverso a partir de la suma. En Python es tentador porque los enteros tienen precisión arbitraria.

Python

def obtener_numero(head):
    num = 0
    lugar = 1
    while head:
        num += head.val * lugar
        lugar *= 10
        head = head.next
    return num

# Luego sumar y reconstruir ... pero no hagas esto.

Complejidad inicial

Esto funciona para entradas pequeñas, pero el problema permite hasta 100 dígitos — números mucho más grandes de lo que puede contener un entero de 64 bits. En lenguajes como C++ o Java se desbordarían inmediatamente. Incluso en Python, no es la idea central: el problema está diseñado para enseñar simulación de acarreo sobre listas ligadas, no bibliotecas de enteros grandes.

Simulando la suma de la primaria

Dado que los dígitos están almacenados en orden inverso (el menos significativo primero), podemos sumar dígito a dígito exactamente como lo hacíamos en la primaria. Recorremos ambas listas juntas, sumamos los dígitos actuales más cualquier acarreo del paso anterior, almacenamos suma % 10 en un nuevo nodo y pasamos suma // 10 a la siguiente posición. Cuando una lista se agota, tratamos los dígitos faltantes como 0. Al final, si queda un acarreo, agregamos un nodo más.

El truco del nodo fantasma (dummy) mantiene el código limpio: nunca necesitamos comprobar si la lista resultado está vacía.

Python

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        actual = dummy
        acarreo = 0

        while l1 or l2 or acarreo:
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0
            total = val1 + val2 + acarreo
            acarreo = total // 10
            actual.next = ListNode(total % 10)
            actual = actual.next

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

        return dummy.next

Sigamos l1 = [2,4,3] , l2 = [5,6,4]:

Simulación paso a paso: l1 = [2,4,3] , l2 = [5,6,4]
Paso dígito l1 dígito l2 Acarreo entrada Suma Dígito salida Acarreo salida Lista resultado
1 2 5 0 7 7 0 [7]
2 4 6 0 10 0 1 [7, 0]
3 3 4 1 8 8 0 [7, 0, 8]
4 — — 0 0 — 0 Terminado → [7,0,8]
El acarreo aparece en el paso 2 y se consume en el paso 3. Después de agotar ambas listas y con acarreo 0, terminamos.

Complejidad final

Complejidad temporal: O(max(m, n)) — recorremos cada nodo exactamente una vez.
Complejidad espacial: O(max(m, n)) para la nueva lista (si ignoramos la salida, el espacio auxiliar es O(1)).

La misma lógica funciona en JavaScript, C++, Go, Kotlin o Swift; solo cambia la sintaxis.

Domina el acarreo y habrás dominado la base de la aritmética de precisión arbitraria.
#1

Referencias y lecturas adicionales

¿No tienes suficiente de lumænaut? Lee esto...