Dados dos números representados por dos listas, escribe una función que devuelva la lista de suma. La lista de suma es una representación de lista de la suma de dos números de entrada.
Ejemplo :
Input:
List1: 5->6->3 // represents number 563
List2: 8->4->2 // represents number 842
Output:
Resultant list: 1->4->0->5 // represents number 1405
Explanation: 563 + 842 = 1405 Input:
List1: 7->5->9->4->6 // represents number 75946
List2: 8->4 // represents number 84
Output:
Resultant list: 7->6->0->3->0// represents number 76030
Explanation: 75946+84=76030
Enfoque : recorra ambas listas y seleccione Nodes uno por uno de ambas listas y agregue los valores. Si la suma es mayor que 10, haga llevar como 1 y reduzca la suma. Si una lista tiene más elementos que la otra, considere los valores restantes de esta lista como 0.
Los pasos son:
- Recorra las dos listas enlazadas de principio a fin
- Agregue los dos dígitos de cada una de las respectivas listas enlazadas.
- Si una de las listas ha llegado al final, tome 0 como su dígito.
- Continúe hasta el final de las listas.
- Si la suma de dos dígitos es mayor que 9, configure el acarreo como 1 y el dígito actual como suma % 10
A continuación se muestra la implementación de este enfoque.
Python
# Python program to add two numbers # represented by linked list # Node class class Node: # Constructor to initialize the # node object def __init__(self, data): self.data = data self.next = None class LinkedList: # Function to initialize head def __init__(self): self.head = None # Function to insert a new node at # the beginning def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node # Add contents of two linked lists and # return the head node of resultant list def addTwoLists(self, first, second): prev = None temp = None carry = 0 # While both list exists while(first is not None or second is not None): # Calculate the value of next digit # in resultant list # The next digit is sum of following # things # (i) Carry # (ii) Next digit of first list (if # there is a next digit) # (iii) Next digit of second list (if # there is a next digit) fdata = 0 if first is None else first.data sdata = 0 if second is None else second.data Sum = carry + fdata + sdata # Update carry for next calculation carry = 1 if Sum >= 10 else 0 # Update sum if it is greater than 10 Sum = Sum if Sum < 10 else Sum % 10 # Create a new node with sum as data temp = Node(Sum) # if this is the first node then set # it as head of resultant list if self.head is None: self.head = temp else: prev.next = temp # Set prev for next insertion prev = temp # Move first and second pointers to # next nodes if first is not None: first = first.next if second is not None: second = second.next if carry > 0: temp.next = Node(carry) # Utility function to print the # linked LinkedList def printList(self): temp = self.head while(temp): print temp.data, temp = temp.next # Driver code first = LinkedList() second = LinkedList() # Create first list first.push(6) first.push(4) first.push(9) first.push(5) first.push(7) print "First List is ", first.printList() # Create second list second.push(4) second.push(8) print " Second List is ", second.printList() # Add the two lists and see result res = LinkedList() res.addTwoLists(first.head, second.head) print " Resultant list is ", res.printList() # This code is contributed by Nikhil Kumar Singh(nickzuck_007)
Producción:
First List is 7 5 9 4 6 Second List is 8 4 Resultant list is 5 0 0 5 6
Análisis de Complejidad:
- Complejidad de tiempo: O(m + n), donde m y n son números de Nodes en la primera y segunda lista respectivamente.
Las listas deben recorrerse una sola vez. - Complejidad espacial: O(m + n).
Se necesita una lista enlazada temporal para almacenar el número de salida
Artículo relacionado: Suma dos números representados por listas enlazadas | conjunto 2
Consulte el artículo completo sobre Agregar dos números representados por listas vinculadas | ¡ Establezca 1 para más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA