Sumar dos listas enlazadas con acarreo

  
Introducción
       
En este artículo, aprenderás a Sumar dos listas enlazadas con acarreo. Este es un problema de programación común que se puede encontrar en entrevistas de trabajo, como las de Facebook.

En este artículo, cubriremos los siguientes temas:

✅ Una explicación del problema
✅ Una solución eficiente
✅ Implementaciones en Java, Python, PHP, C++ y JavaScript

                       
Problema
Dadas dos listas enlazadas, genere una tercera que tenga la suma de los elementos nodo a nodo, y que el elemento sobrante o acarreo lo sume al siguiente nodo.


        
Pasos para realizar el ejercicio:
1.-  Crear un puntero head3.

2.- Declaramos acarreo en cero.
        
3.- Recorremos ambas listas, mientras alguna no sea null.
        
4.- Declaramos suma con el valor de acarreo.

5.- Si existe alguno de los 2 punteros, lo sumamos a suma y lo movemos a la siguiente posición de la lista.
           
6.- El acarreo lo dividimos entre diez.

7.- Insertamos el módulo diez de la suma resultante en la lista 3.

8.- Una vez que salimos del ciclo, verificamos si existe un acarreo, si es así, insertamos el valor en la lista.

9.- Retornamos la lista enlazada 3.

Código en Java

public class Solution {

    public ListNode crearNodo(int val) {
        ListNode nodo = new ListNode(val);
        return nodo;
    }

    public ListNode insercion(ListNode head, int val) {
        ListNode newListNode = crearNodo(val);

        if (head == null) {
            head = newListNode;
        } else {
            ListNode actual = head;
            while (actual.next != null) {
                actual = actual.next;
            }
            actual.next = newListNode;
        }

        return head;
    }

    public ListNode addTwoNumbers(ListNode head1, ListNode head2) {
        ListNode head3 = null;
        int acarreo = 0;

        while (head1 != null || head2 != null) {
            int suma = acarreo;
            if (head1 != null) {
                suma += head1.val;
                head1 = head1.next;
            }

            if (head2 != null) {
                suma += head2.val;
                head2 = head2.next;
            }

            acarreo = suma / 10;
            head3 = insercion(head3, suma % 10);
        }

        if (acarreo > 0) {
            head3 = insercion(head3, acarreo);
        }

        return head3;
    }
}

Código en php

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {

     public function crearNodo($val) {
        $nodo = new ListNode($val);
        return $nodo;
    }

    public function insercion($head, $val) {
        $nuevoNodo = $this->crearNodo($val);

        if ($head === null) {
            $head = $nuevoNodo;
        } else {
            $actual = $head;
            while ($actual->next !== null) {
                $actual = $actual->next;
            }
            $actual->next = $nuevoNodo;
        }

        return $head;
    }

    public function addTwoNumbers($head1, $head2) {
        $head3 = null;
        $acarreo = 0;

        while ($head1 || $head2) {
            $suma = $acarreo;
            if ($head1) {
                $suma += $head1->val;
                $head1 = $head1->next;
            }

            if ($head2) {
                $suma += $head2->val;
                $head2 = $head2->next;
            }

            $acarreo = floor($suma / 10);
            $head3 = $this->insercion($head3, $suma % 10);
        }

        if ($acarreo > 0) {
            $head3 = $this->insercion($head3, $acarreo);
        }

        return $head3;
    }
}

 

Código en Python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def crearNodo(self, val):
        nodo = ListNode(val)
        return nodo

    def insercion(self, head, val):
        nuevoNodo = self.crearNodo(val)

        if not head:
            head = nuevoNodo
        else:
            actual = head
            while actual.next:
                actual = actual.next
            actual.next = nuevoNodo

        return head

    def addTwoNumbers(self, head1, head2):
        head3 = None
        acarreo = 0

        while head1 or head2:
            suma = acarreo
            if head1:
                suma += head1.val
                head1 = head1.next
            if head2:
                suma += head2.val
                head2 = head2.next

            acarreo = suma // 10
            head3 = self.insercion(head3, suma % 10)

        if acarreo > 0:
            head3 = self.insercion(head3, acarreo)

        return head3

Código en C++

/**
 * 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* crearNodo(int val) {
		ListNode *nodo 	= new ListNode;
		nodo->val=val;
  		nodo->next 	= NULL;
  		return nodo;
	}

    ListNode* insercion(ListNode* head, int val) {
    	ListNode* newlistNode = crearNodo(val);

	    if (head == NULL)  head = newlistNode;
		else {
	      ListNode* actual = head;
	      while (actual->next != NULL) {
	        actual = actual->next;
	      }
	      actual->next = newlistNode;
	    }
	    
	    return head;
    }

    ListNode* addTwoNumbers(ListNode* head1, ListNode* head2) {
        ListNode* head3 = nullptr;
		int acarreo = 0;
		
		while(head1 || head2){
			int suma = acarreo;
			if(head1){
				suma += head1->val;
				head1 = head1->next;
			}
	
			if(head2){
				suma += head2->val;
				head2 = head2->next;
			}

			acarreo = suma / 10;
			head3 = insercion(head3,suma%10);
			
		}
		
		if(acarreo>0) head3 = insercion(head3,acarreo);
		
		
		return head3;
    }
};

Código en JavaScript

  var crearNodo = function (val) {
    return new ListNode(val);
  }

 var insercion= function(head, val) {
    const newNode = crearNodo(val);

    if (!head) {
      head = newNode;
    } else {
      let current = head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }

    return head;
  }
var addTwoNumbers = function(head1, head2) {
      let head3 = null;
    let carry = 0;

    while (head1 || head2) {
      let sum = carry;
      if (head1) {
        sum += head1.val;
        head1 = head1.next;
      }

      if (head2) {
        sum += head2.val;
        head2 = head2.next;
      }

      carry = Math.floor(sum / 10);
      head3 = insercion(head3, sum % 10);
    }

    if (carry > 0) {
      head3 = insercion(head3, carry);
    }

    return head3;
};

        
    
Conclusión
En este artículo, aprendiste a Sumar dos listas enlazadas. Este es un problema de programación común que se puede encontrar en entrevistas de trabajo, como las de Facebook.