Add Two Numbers

Last updated Apr 29, 2023 Edit Source

• Interviewprep
• Leetcode

Este problema es bastante simple, pero tiene sus gotchas. El problema dice asi:

Dada dos listas enlazadas, las cuales, solo pueden guardar integers. Determina la suma de ellas, toma en cuenta que estas se encuentran de reversa, de modo que, una lista como [3, 4, 5] en realidad representa el numero 543.

Este es un problema con su complejidad, desde que las listas se encuentran invertidas hasta los calculos para determinar cada caso especifico.

Antes de codificar la solucion, debemos entender el problema. Para ello, un ejemplo es lo mejor. La suma de las listas [2, 4, 3] + [5, 6, 4] da como resultado 807, numero el cual, debe ser representado al final igualmente como una lista enlazada, de modo que tendriamos la lista: [7, 0, 8].

Para resolver este problema, podemos tomar dos acercamientos, invertir las listas y hacer los calculos o utilizar un poco de matematica con modulos y divisiones para hacer los calculos.

Una cosa a tomar bastante en cuenta es utilizar sumas simples desde 0-9 haciendose cargo del caso especial en caso de que quede un remainder al hacer la suma de estos (Como de 12, hacerse cargo del 2 y del 1 en la suma para el siguiente nodo). De esta forma, se logran sumar valores que exceden el limite de los lenguajes (numeros de 32 y 64 bits).

Mi solucion va asi:

1. Definimos una variable first para representar el primer nodo de la lista que sera regresado al final para la respuesta, se inicializa con None
2. Se define una variable r que representa el reminader para los casos cuando tengamos valores mayores o iguales a 10
3. Se define una variable resp para mantener el control del avance en la lista de respuesta
4. Se definen dos nodos, el node1 y el node2, que representaran los nodos actuales al iterar sobre las listas
5. Se entra en un ciclo, del cual no se saldra hasta que ambos node1 y node2 sean None, para entonces, se habra iterado sobre las listas
6. Primero se checa si el node1 se encuentra en None. Si es asi, el valor de este para la suma es 0. Si no, se utiliza el valor y se actualiza el node a ser el siguiente.
7. Se hace el mismo chequeo con node2
8. Ahora hacemos la suma de dichos valores que acabamos de obtener de los nodos. Tomamos en consideracion los casos cuando el remainder r es mayor que 0, en tal caso, lo agregaremos a la suma y lo reiniciaremos. Caso contrario, hacemos una suma normal solo considerando los dos valores de los nodos
9. Siguiente consideramos el caso en el cual la suma ha sido mayor que 9 (Mayor o igual que 10). Para dicho caso, calculamos el remainder y el nuevo valor de la suma, quitandole 10.
10. Ahora procedemos a construir la lista de respuesta, si resp es None, significa que estamos en la primer iteracion, por tanto, colocamos un nuevo nodo como resp e inicializamos first para ser este mismo nodo, puesto que, siempre sera el primero. Caso contrario, simplemente actualizamos el siguiente nodo de la lista resp y actualizamos resp para que apunte a dicho nodo que acabamos de crear.
11. Casi terminando, salimos del bucle, a este punto ya iteramos sobre ambas listas de nodos, solo nos queda tratar en caso de que, al final, tengamos un valor r todavia guardado, en dicho caso, solo nos queda almacenar este ultimo valor en un nodo y actualizar como en el paso anterior.
12. Finalmente, retornamos el primer nodo, o la cabeza de la lista, a partir de la cual podemos obtener todo el resto de nodos

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        first = None
        r = 0
        resp = None
        node1 = l1
        node2 = l2

        while node1 or node2:
            if node1 == None:
                v1 = 0
            else:
                v1 = node1.val
                node1 = node1.next

            if node2 == None:
                v2 = 0
            else:
                v2 = node2.val
                node2 = node2.next

            if r > 0:
                s = v1 + v2 + r
                r = 0
            else:
                s = v1 + v2

            if s > 9:
                r = int(s/10)
                s = int(s%10)

            if resp == None:
                resp = ListNode(s, None)
                first = resp

            else:
                resp.next = ListNode(s, None)
                resp = resp.next

        if r > 0:
            resp.next = ListNode(r, None)
            resp = resp.next

        return first