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.
C
// C program to implement the
// above approach
#include <stdio.h>
#include <stdlib.h>
// Linked list node
struct Node
{
int data;
struct Node* next;
};
/* Function to create a new node
with given data */
struct Node* newNode(int data)
{
struct Node* new_node =
(struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
new_node->next = NULL;
return new_node;
}
/* Function to insert a node at the
beginning of the Singly Linked List */
void push(struct Node** head_ref,
int new_data)
{
// Allocate node
struct Node* new_node = newNode(new_data);
// Link the old list off the new node
new_node->next = (*head_ref);
// Move the head to point to the
// new node
(*head_ref) = new_node;
}
/* Adds contents of two linked
lists and return the head node
of resultant list */
struct Node* addTwoLists(struct Node* first,
struct Node* second)
{
// res is head node of the resultant
// list
struct Node* res = NULL;
struct Node *temp, *prev = NULL;
int carry = 0, sum;
// while both lists exist
while (first != NULL ||
second != NULL)
{
// Calculate 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)
// (ii) Next digit of second
// list (if there is a next digit)
sum = carry + (first ? first->data : 0) +
(second ? second->data : 0);
// Update carry for next calculation
carry = (sum >= 10) ? 1 : 0;
// Update sum if it is greater than 10
sum = sum % 10;
// Create a new node with sum as data
temp = newNode(sum);
// If this is the first node then
// set it as head of the resultant
// list
if (res == NULL)
res = temp;
// If this is not the first node
// then connect it to the rest.
else
prev->next = temp;
// Set prev for next insertion
prev = temp;
// Move first and second pointers to
// next nodes
if (first)
first = first->next;
if (second)
second = second->next;
}
if (carry > 0)
temp->next = newNode(carry);
// return head of the resultant list
return res;
}
// A utility function to print a
// linked list
void printList(struct Node* node)
{
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
printf("");
}
// Driver code
int main(void)
{
struct Node* res = NULL;
struct Node* first = NULL;
struct Node* second = NULL;
// Create first list 7->5->9->4->6
push(&first, 6);
push(&first, 4);
push(&first, 9);
push(&first, 5);
push(&first, 7);
printf("First List is ");
printList(first);
// Create second list 8->4
push(&second, 4);
push(&second, 8);
printf("Second List is ");
printList(second);
// Add the two lists and see result
res = addTwoLists(first, second);
printf("Resultant list is ");
printList(res);
return 0;
}
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
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