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 :
Entrada:
Lista1: 5->6->3 // representa el número 563
Lista2: 8->4->2 // representa el número 842
Salida:
Lista resultante: 1->4->0->5 // representa el número 1405
Explicación: 563 + 842 = 1405Entrada:
List1: 7->5->9->4->6 // representa el número 75946
List2: 8->4 // representa el número 84
Salida:
Lista resultante: 7->6->0->3-> 0// representa el número 76030
Explicación: 75946+84=76030
Enfoque : recorrer ambas listas hasta el final y agregar ceros anteriores en la lista con dígitos menores. Luego llame a una función recursiva en los Nodes de inicio de ambas listas que se llama a sí misma para los siguientes Nodes de ambas listas hasta que llega al final. Esta función crea un Node para la suma de los dígitos actuales y devuelve el acarreo.
Los pasos son:
- Recorra las dos listas vinculadas para agregar ceros anteriores en caso de que una lista tenga menos dígitos que la otra.
- Comience desde el Node principal de ambas listas y llame a una función recursiva para los siguientes Nodes.
- Continúe hasta el final de las listas.
- Crea un Node para la suma de dígitos actuales y devuelve el acarreo.
A continuación se muestra la implementación de este enfoque.
C++
// C++ program to add two numbers
// represented by linked list
#include <bits/stdc++.h>
using namespace std;
/* Linked list node */
class Node {
public:
int data;
Node* next;
};
/* Function to create a
new node with given data */
Node* newNode(int data)
{
Node* new_node = new 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(Node** head_ref, int new_data)
{
/* allocate node */
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 */
Node* addTwoLists(Node* first, Node* second)
{
// res is head node of the resultant list
Node* res = NULL;
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;
}
Node* reverse(Node* head)
{
if (head == NULL || head->next == NULL)
return head;
// reverse the rest list and put the first element at the end
Node* rest = reverse(head->next);
head->next->next = head;
head->next = NULL;
// fix the head pointer
return rest;
}
// A utility function to print a linked list
void printList(Node* node)
{
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
/* Driver code */
int main(void)
{
Node* res = NULL;
Node* first = NULL;
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);
cout << "Second List is ";
printList(second);
// reverse both the lists
first = reverse(first);
second = reverse(second);
// Add the two lists
res = addTwoLists(first, second);
// reverse the res to get the sum
res = reverse(res);
cout << "Resultant list is ";
printList(res);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to add two numbers
// represented by linked list
#include <stdio.h>
#include <stdlib.h>
/* Linked list node */
typedef struct Node {
int data;
struct Node* next;
}Node;
/* Function to create a
new node with given data */
Node* newNode(int data)
{
Node* new_node = (Node *)malloc(sizeof(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(Node** head_ref, int new_data)
{
/* allocate node */
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 */
Node* addTwoLists(Node* first, Node* second)
{
// res is head node of the resultant list
Node* res = NULL;
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;
}
Node* reverse(Node* head)
{
if (head == NULL || head->next == NULL)
return head;
// reverse the rest list and put the first element at the end
Node* rest = reverse(head->next);
head->next->next = head;
head->next = NULL;
// fix the head pointer
return rest;
}
// A utility function to print a linked list
void printList(Node* node)
{
while (node != NULL) {
printf("%d ",node->data);
node = node->next;
}
printf("\n");
}
/* Driver code */
int main(void)
{
Node* res = NULL;
Node* first = NULL;
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);
// reverse both the lists
first = reverse(first);
second = reverse(second);
// Add the two lists
res = addTwoLists(first, second);
// reverse the res to get the sum
res = reverse(res);
printf("Resultant list is ");
printList(res);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to add two numbers
// represented by linked list
class LinkedList {
static Node head1, head2;
static class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
/* Adds contents of two linked lists and prints it */
void addTwoLists(Node first, Node second) {
Node start1 = new Node(0);
start1.next = first;
Node start2 = new Node(0);
start2.next = second;
addPrecedingZeros(start1, start2);
Node result = new Node(0);
if (sumTwoNodes(start1.next, start2.next, result) == 1) {
Node node = new Node(1);
node.next = result.next;
result.next = node;
}
printList(result.next);
}
/* Adds lists and returns the carry */
private int sumTwoNodes(Node first, Node second, Node result) {
if (first == null) {
return 0;
}
int number = first.data + second.data + sumTwoNodes(first.next, second.next, result);
Node node = new Node(number % 10);
node.next = result.next;
result.next = node;
return number / 10;
}
/* Appends preceding zeros in case a list is having lesser nodes than the other one*/
private void addPrecedingZeros(Node start1, Node start2) {
Node next1 = start1.next;
Node next2 = start2.next;
while (next1 != null && next2 != null) {
next1 = next1.next;
next2 = next2.next;
}
if (next1 == null && next2 != null) {
while (next2 != null) {
Node node = new Node(0);
node.next = start1.next;
start1.next = node;
next2 = next2.next;
}
} else if (next2 == null && next1 != null) {
while (next1 != null) {
Node node = new Node(0);
node.next = start2.next;
start2.next = node;
next1 = next1.next;
}
}
}
/* Utility function to print a linked list */
void printList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println("");
}
// Driver Code
public static void main(String[] args) {
LinkedList list = new LinkedList();
// creating first list
list.head1 = new Node(7);
list.head1.next = new Node(5);
list.head1.next.next = new Node(9);
list.head1.next.next.next = new Node(4);
list.head1.next.next.next.next = new Node(6);
System.out.print("First List is ");
list.printList(head1);
// creating second list
list.head2 = new Node(8);
list.head2.next = new Node(4);
System.out.print("Second List is ");
list.printList(head2);
System.out.print("Resultant List is ");
// add the two lists and see the result
list.addTwoLists(head1, head2);
}
// this code is contributed by *Saurabh321Gupta*
}
C#
// C# program to add two numbers
// represented by linked list
using System;
public class List {
public class Node {
public int data;
public Node next;
public Node(int d) {
data = d;
next = null;
}
}
public static Node head1, head2;
/* Adds contents of two linked lists and prints it */
public void addTwoLists(Node first, Node second) {
Node start1 = new Node(0);
start1.next = first;
Node start2 = new Node(0);
start2.next = second;
addPrecedingZeros(start1, start2);
Node result = new Node(0);
if (sumTwoNodes(start1.next, start2.next, result) == 1) {
Node node = new Node(1);
node.next = result.next;
result.next = node;
}
printList(result.next);
}
/* Adds lists and returns the carry */
public int sumTwoNodes(Node first, Node second, Node result) {
if (first == null) {
return 0;
}
int number = first.data + second.data + sumTwoNodes(first.next, second.next, result);
Node node = new Node(number % 10);
node.next = result.next;
result.next = node;
return number / 10;
}
/*
* Appends preceding zeros in case a list is having lesser nodes than the other
* one
*/
public void addPrecedingZeros(Node start1, Node start2) {
Node next1 = start1.next;
Node next2 = start2.next;
while (next1 != null && next2 != null) {
next1 = next1.next;
next2 = next2.next;
}
if (next1 == null && next2 != null) {
while (next2 != null) {
Node node = new Node(0);
node.next = start1.next;
start1.next = node;
next2 = next2.next;
}
} else if (next2 == null && next1 != null) {
while (next1 != null) {
Node node = new Node(0);
node.next = start2.next;
start2.next = node;
next1 = next1.next;
}
}
}
/* Utility function to print a linked list */
public void printList(Node head) {
while (head != null) {
Console.Write(head.data + " ");
head = head.next;
}
Console.WriteLine("");
}
// Driver Code
public static void Main(String[] args) {
List list = new List();
// creating first list
Node head1 = new Node(7);
head1.next = new Node(5);
head1.next.next = new Node(9);
head1.next.next.next = new Node(4);
head1.next.next.next.next = new Node(6);
Console.Write("First List is ");
list.printList(head1);
// creating second list
Node head2 = new Node(8);
head2.next = new Node(4);
Console.Write("Second List is ");
list.printList(head2);
Console.Write("Resultant List is ");
// add the two lists and see the result
list.addTwoLists(head1, head2);
}
}
// This code is contributed by umadevi9616
Producción
First List is 7 5 9 4 6 Second List is 8 4 Resultant list is 7 6 0 3 0
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
Método 2 (usando STL): usando la estructura de datos de la pila
Acercarse :
- Cree 3 pilas, a saber, s1, s2, s3.
- Rellene s1 con Nodes de lista1 y rellene s2 con Nodes de lista2.
- Rellene s3 creando nuevos Nodes y configurando los datos de los nuevos Nodes en la suma de s1.top(), s2.top() y lleve hasta que list1 y list2 estén vacíos.
- Si la suma >9
- conjunto llevar 1
- más
- establecer llevar 0
- Cree un Node (por ejemplo, anterior) que contendrá el encabezado de la Lista de suma.
- Vincular todos los elementos de s3 de arriba a abajo
- volver anterior
Código:
C++
// C++ program to add two numbers represented by Linked
// Lists using Stack
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
};
Node* newnode(int data)
{
Node* x = new Node();
x->data = data;
return x;
}
// function that returns the sum of two numbers represented
// by linked lists
Node* addTwoNumbers(Node* l1, Node* l2)
{
Node* prev = NULL;
// Create 3 stacks
stack<Node*> s1, s2, s3;
// Fill first stack with first List Elements
while (l1 != NULL) {
s1.push(l1);
l1 = l1->next;
}
// Fill second stack with second List Elements
while (l2 != NULL) {
s2.push(l2);
l2 = l2->next;
}
int carry = 0;
// Fill the third stack with the sum of first and second
// stack
while (!s1.empty() && !s2.empty()) {
int sum = s1.top()->data + s2.top()->data + carry;
Node* temp = newnode(sum % 10);
s3.push(temp);
if (sum > 9) {
carry = 1;
}
else {
carry = 0;
}
s1.pop();
s2.pop();
}
while (!s1.empty()) {
int sum = carry + s1.top()->data;
Node* temp = newnode(sum % 10);
s3.push(temp);
if (sum > 9) {
carry = 1;
}
else {
carry = 0;
}
s1.pop();
}
while (!s2.empty()) {
int sum = carry + s2.top()->data;
Node* temp = newnode(sum % 10);
s3.push(temp);
if (sum > 9) {
carry = 1;
}
else {
carry = 0;
}
s2.pop();
}
// If carry is still present create a new node with
// value 1 and push it to the third stack
if (carry == 1) {
Node* temp = newnode(1);
s3.push(temp);
}
// Link all the elements inside third stack with each
// other
if (!s3.empty())
prev = s3.top();
while (!s3.empty()) {
Node* temp = s3.top();
s3.pop();
if (s3.size() == 0) {
temp->next = NULL;
}
else {
temp->next = s3.top();
}
}
return prev;
}
// utility functions
// Function that displays the List
void Display(Node* head)
{
if (head == NULL) {
return;
}
while (head->next != NULL) {
cout << head->data << " -> ";
head = head->next;
}
cout << head->data << endl;
}
// Function that adds element at the end of the Linked List
void push(Node** head_ref, int d)
{
Node* new_node = newnode(d);
new_node->next = NULL;
if (*head_ref == NULL) {
new_node->next = *head_ref;
*head_ref = new_node;
return;
}
Node* last = *head_ref;
while (last->next != NULL && last != NULL) {
last = last->next;
}
last->next = new_node;
return;
}
// Driver Program for above Functions
int main()
{
// Creating two lists
// first list = 9 -> 5 -> 0
// second List = 6 -> 7
Node* first = NULL;
Node* second = NULL;
Node* sum = NULL;
push(&first, 7);
push(&first, 5);
push(&first, 9);
push(&first, 4);
push(&first, 6);
push(&second, 8);
push(&second, 4);
cout << "First List : ";
Display(first);
cout << "Second List : ";
Display(second);
sum = addTwoNumbers(first, second);
cout << "Sum List : ";
Display(sum);
return 0;
}
Java
// Java program to add two numbers represented by Linked
// Lists using Stack
import java.util.*;
class LinkedList {
static Node head1, head2;
static class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
// function that calculates and prints the sum of two numbers represented
// by linked lists
static void addTwoLists(Node l1, Node l2)
{
Node prev = null;
// Create 3 stacks
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();
Stack<Node> s3 = new Stack<Node>();
// Fill first stack with first List Elements
while (l1 != null) {
s1.add(l1);
l1 = l1.next;
}
// Fill second stack with second List Elements
while (l2 !=null) {
s2.add(l2);
l2 = l2.next;
}
int carry = 0;
// Fill the third stack with the sum of first and second
// stack
while (!s1.isEmpty() && !s2.isEmpty()) {
int sum = s1.peek().data + s2.peek().data + carry;
Node temp = new Node(sum % 10);
s3.add(temp);
if (sum > 9) {
carry = 1;
}
else {
carry = 0;
}
s1.pop();
s2.pop();
}
while (!s1.isEmpty()) {
int sum = carry + s1.peek().data;
Node temp = new Node(sum % 10);
s3.add(temp);
if (sum > 9) {
carry = 1;
}
else {
carry = 0;
}
s1.pop();
}
while (!s2.isEmpty()) {
int sum = carry + s2.peek().data;
Node temp = new Node(sum % 10);
s3.add(temp);
if (sum > 9) {
carry = 1;
}
else {
carry = 0;
}
s2.pop();
}
// If carry is still present create a new node with
// value 1 and push it to the third stack
if (carry == 1) {
Node temp = new Node(1);
s3.add(temp);
}
// Link all the elements inside third stack with each
// other
if (!s3.isEmpty())
prev = s3.peek();
while (!s3.isEmpty()) {
Node temp = s3.peek();
s3.pop();
if (s3.size() == 0) {
temp.next = null;
}
else {
temp.next = s3.peek();
}
}
printList(prev);
}
/* Utility function to print a linked list */
static void printList(Node head) {
while (head != null) {
System.out.print(head.data + " -> ");
head = head.next;
}
System.out.println("");
}
// Driver Code
public static void main(String[] args) {
LinkedList list = new LinkedList();
// creating first list
list.head1 = new Node(7);
list.head1.next = new Node(5);
list.head1.next.next = new Node(9);
list.head1.next.next.next = new Node(4);
list.head1.next.next.next.next = new Node(6);
System.out.print("First List : ");
list.printList(head1);
// creating second list
list.head2 = new Node(8);
list.head2.next = new Node(4);
System.out.print("Second List : ");
list.printList(head2);
System.out.print("Sum List : ");
// add the two lists and see the result
list.addTwoLists(head1, head2);
}
// this code is contributed by Abhijeet Kumar(abhijeet19403)
}
C#
// C# program to add two numbers represented by Linked
// Lists using Stack
using System;
using System.Collections.Generic;
public class List {
public class Node {
public int data;
public Node next;
public Node(int d) {
data = d;
next = null;
}
}
public static Node head1, head2;
// function that calculates and prints the sum of two numbers represented
// by linked lists
public void addTwoLists(Node l1, Node l2)
{
Node prev = null;
// Create 3 stacks
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();
Stack<Node> s3 = new Stack<Node>();
// Fill first stack with first List Elements
while (l1 != null) {
s1.Push(l1);
l1 = l1.next;
}
// Fill second stack with second List Elements
while (l2 !=null) {
s2.Push(l2);
l2 = l2.next;
}
int carry = 0;
// Fill the third stack with the sum of first and second
// stack
while (s1.Count!=0 && s2.Count!=0) {
int sum = s1.Peek().data + s2.Peek().data + carry;
Node temp = new Node(sum % 10);
s3.Push(temp);
if (sum > 9) {
carry = 1;
}
else {
carry = 0;
}
s1.Pop();
s2.Pop();
}
while (s1.Count!=0) {
int sum = carry + s1.Peek().data;
Node temp = new Node(sum % 10);
s3.Push(temp);
if (sum > 9) {
carry = 1;
}
else {
carry = 0;
}
s1.Pop();
}
while (s2.Count!=0) {
int sum = carry + s2.Peek().data;
Node temp = new Node(sum % 10);
s3.Push(temp);
if (sum > 9) {
carry = 1;
}
else {
carry = 0;
}
s2.Pop();
}
// If carry is still present create a new node with
// value 1 and push it to the third stack
if (carry == 1) {
Node temp = new Node(1);
s3.Push(temp);
}
// Link all the elements inside third stack with each
// other
if (s3.Count!=0)
prev = s3.Peek();
while (s3.Count!=0) {
Node temp = s3.Peek();
s3.Pop();
if (s3.Count == 0) {
temp.next = null;
}
else {
temp.next = s3.Peek();
}
}
printList(prev);
}
/* Utility function to print a linked list */
public void printList(Node head) {
while (head != null) {
Console.Write(head.data + " -> ");
head = head.next;
}
Console.WriteLine("");
}
// Driver Code
public static void Main(String[] args) {
List list = new List();
// creating first list
Node head1 = new Node(7);
head1.next = new Node(5);
head1.next.next = new Node(9);
head1.next.next.next = new Node(4);
head1.next.next.next.next = new Node(6);
Console.Write("First List : ");
list.printList(head1);
// creating second list
Node head2 = new Node(8);
head2.next = new Node(4);
Console.Write("Second List : ");
list.printList(head2);
Console.Write("Resultant List : ");
// add the two lists and see the result
list.addTwoLists(head1, head2);
}
}
// This code is contributed by Abhijeet Kumar(abhijeet19403)
Producción
First List : 7 -> 5 -> 9 -> 4 -> 6 Second List : 8 -> 4 Sum List : 7 -> 6 -> 0 -> 3 -> 0
Complejidad de tiempo: O(n)
Aquí n es la longitud de la lista más grande
Espacio Auxiliar: O(n)
Se utiliza espacio adicional para almacenar los elementos en la pila.
Otro enfoque con complejidad temporal O(N):
El enfoque dado funciona como los siguientes pasos:
- Primero, calculamos los tamaños de ambas listas enlazadas, size1 y size2, respectivamente.
- Luego recorremos la lista enlazada más grande, si la hay, y disminuimos hasta que el tamaño de ambos sea el mismo.
- Ahora recorremos ambas listas enlazadas hasta el final.
- Ahora el retroceso ocurre mientras se realiza la suma.
- Finalmente, el Node principal se devuelve a la lista enlazada que contiene la respuesta.
C++
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node* next;
};
// recursive function
Node* addition(Node* temp1, Node* temp2, int size1,
int size2)
{
// creating a new Node
Node* newNode
= (struct Node*)malloc(sizeof(struct Node));
// base case
if (temp1->next == NULL && temp2->next == NULL) {
// addition of current nodes which is the last nodes
// of both linked lists
newNode->data = (temp1->data + temp2->data);
// set this current node's link null
newNode->next = NULL;
// return the current node
return newNode;
}
// creating a node that contains sum of previously added
// number
Node* returnedNode
= (struct Node*)malloc(sizeof(struct Node));
// if sizes are same then we move in both linked list
if (size2 == size1) {
// recursively call the function
// move ahead in both linked list
returnedNode = addition(temp1->next, temp2->next,
size1 - 1, size2 - 1);
// add the current nodes and append the carry
newNode->data = (temp1->data + temp2->data)
+ ((returnedNode->data) / 10);
}
// or else we just move in big linked list
else {
// recursively call the function
// move ahead in big linked list
returnedNode = addition(temp1, temp2->next, size1,
size2 - 1);
// add the current node and carry
newNode->data
= (temp2->data) + ((returnedNode->data) / 10);
}
// this node contains previously added numbers
// so we need to set only rightmost digit of it
returnedNode->data = (returnedNode->data) % 10;
// set the returned node to the current node
newNode->next = returnedNode;
// return the current node
return newNode;
}
// Function to add two numbers represented by nexted list.
struct Node* addTwoLists(struct Node* head1,
struct Node* head2)
{
struct Node *temp1, *temp2, *ans = NULL;
temp1 = head1;
temp2 = head2;
int size1 = 0, size2 = 0;
// calculating the size of first linked list
while (temp1 != NULL) {
temp1 = temp1->next;
size1++;
}
// calculating the size of second linked list
while (temp2 != NULL) {
temp2 = temp2->next;
size2++;
}
Node* returnedNode
= (struct Node*)malloc(sizeof(struct Node));
// traverse the bigger linked list
if (size2 > size1) {
returnedNode = addition(head1, head2, size1, size2);
}
else {
returnedNode = addition(head2, head1, size2, size1);
}
// creating new node if head node is >10
if (returnedNode->data >= 10) {
ans = (struct Node*)malloc(sizeof(struct Node));
ans->data = (returnedNode->data) / 10;
returnedNode->data = returnedNode->data % 10;
ans->next = returnedNode;
}
else
ans = returnedNode;
// return the head node of linked list that contains
// answer
return ans;
}
void Display(Node* head)
{
if (head == NULL) {
return;
}
while (head->next != NULL) {
cout << head->data << " -> ";
head = head->next;
}
cout << head->data << endl;
}
// Function that adds element at the end of the Linked List
void push(Node** head_ref, int d)
{
Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
new_node->data = d;
new_node->next = NULL;
if (*head_ref == NULL) {
new_node->next = *head_ref;
*head_ref = new_node;
return;
}
Node* last = *head_ref;
while (last->next != NULL && last != NULL) {
last = last->next;
}
last->next = new_node;
return;
}
// Driver Program for above Functions
int main()
{
// Creating two lists
Node* first = NULL;
Node* second = NULL;
Node* sum = NULL;
push(&first, 7);
push(&first, 5);
push(&first, 9);
push(&first, 4);
push(&first, 6);
push(&second, 8);
push(&second, 4);
cout << "First List : ";
Display(first);
cout << "Second List : ";
Display(second);
sum = addTwoLists(first, second);
cout << "Sum List : ";
Display(sum);
return 0;
}
// This code is contributed by Dharmik Parmar
Java
import java.util.*;
class GFG{
static class Node {
int data;
Node next;
};
// recursive function
static Node addition(Node temp1, Node temp2, int size1,
int size2)
{
// creating a new Node
Node newNode= new Node();
// base case
if (temp1!=null && temp2!=null && temp1.next == null && temp2.next == null) {
// addition of current nodes which is the last nodes
// of both linked lists
newNode.data = (temp1.data + temp2.data);
// set this current node's link null
newNode.next = null;
// return the current node
return newNode;
}
// creating a node that contains sum of previously added
// number
Node returnedNode = new Node();
// if sizes are same then we move in both linked list
if ((temp1!=null && temp2!=null) && size2 == size1) {
// recursively call the function
// move ahead in both linked list
returnedNode = addition(temp1.next, temp2.next,
size1 - 1, size2 - 1);
// add the current nodes and append the carry
newNode.data = (temp1.data + temp2.data)
+ ((returnedNode.data) / 10);
}
// or else we just move in big linked list
else if(temp1!=null && temp2!=null){
// recursively call the function
// move ahead in big linked list
returnedNode = addition(temp1, temp2.next, size1,
size2 - 1);
// add the current node and carry
newNode.data
= (temp2.data) + ((returnedNode.data) / 10);
}
// this node contains previously added numbers
// so we need to set only rightmost digit of it
returnedNode.data = (returnedNode.data) % 10;
// set the returned node to the current node
newNode.next = returnedNode;
// return the current node
return newNode;
}
// Function to add two numbers represented by nexted list.
static Node addTwoLists(Node head1,
Node head2)
{
Node temp1, temp2, ans = null;
temp1 = head1;
temp2 = head2;
int size1 = 0, size2 = 0;
// calculating the size of first linked list
while (temp1 != null) {
temp1 = temp1.next;
size1++;
}
// calculating the size of second linked list
while (temp2 != null) {
temp2 = temp2.next;
size2++;
}
Node returnedNode
= new Node();
// traverse the bigger linked list
if (size2 > size1) {
returnedNode = addition(head1, head2, size1, size2);
}
else {
returnedNode = addition(head2, head1, size2, size1);
}
// creating new node if head node is >10
if (returnedNode.data >= 10) {
ans = new Node();
ans.data = (returnedNode.data) / 10;
returnedNode.data = returnedNode.data % 10;
ans.next = returnedNode;
}
else
ans = returnedNode;
// return the head node of linked list that contains
// answer
return ans;
}
static void Display(Node head)
{
if (head == null) {
return;
}
while (head.next != null) {
System.out.print(head.data+ "->");
head = head.next;
}
System.out.print(head.data +"\n");
}
// Function that adds element at the end of the Linked List
static Node push(Node head_ref, int d)
{
Node new_node
= new Node();
new_node.data = d;
new_node.next = null;
if (head_ref == null) {
new_node.next = head_ref;
head_ref = new_node;
return head_ref;
}
Node last = head_ref;
while (last.next != null && last != null) {
last = last.next;
}
last.next = new_node;
return head_ref;
}
// Driver Program for above Functions
public static void main(String[] args)
{
// Creating two lists
Node first = null;
Node second = null;
Node sum = null;
first = push(first, 7);
first = push(first, 5);
first = push(first, 9);
first = push(first, 4);
first = push(first, 6);
second = push(second, 8);
second = push(second, 4);
System.out.print("First List : ");
Display(first);
System.out.print("Second List : ");
Display(second);
sum = addTwoLists(first, second);
System.out.print("Sum List : ");
Display(sum);
}
}
// This code contributed by shikhasingrajput
Producción
First List : 7 -> 5 -> 9 -> 4 -> 6 Second List : 8 -> 4 Sum List : 7 -> 6 -> 0 -> 3 -> 0
Artículo relacionado: Suma dos números representados por listas enlazadas | conjunto 2
Escriba comentarios si encuentra que los códigos/algoritmos anteriores son incorrectos o encuentra otras formas de resolver el mismo problema.
Otro enfoque con código fácil de entender (sin añadir ceros)-
En este enfoque simulamos cómo en realidad sumamos dos números. En el código hemos tomado 9->8->7 y 1->2->3 como dos números a sumar. Lo que hacemos es invertir estas dos listas para obtener 7->8->9 y 3->2->1 y comenzar desde el principio de las listas para agregar números de Nodes individuales como lo haríamos en la práctica si sumamos dos números.
Por ejemplo, primero sumamos 7 y 3 para obtener 10, lo que significa llevar = 1 y el valor del nuevo Node será 0. Ahora continuamos con esto hasta el final de la lista.
Pasos-
- Invierta las dos listas de números.
- Simule la adición en los Nodes uno por uno. Agregue cada Node antes de los Nodes de suma ya calculados (comprenderá mejor este paso en el código)
- Al final obtendremos la respuesta final y podremos devolver el Node principal.
C++
// C++ Code to add two nodes by reversing the two lists
#include <bits/stdc++.h>
using namespace std;
/* Linked list Node */
struct Node {
int data;
struct Node* next;
};
Node* newNode(int data)
{
Node* new_node = (Node*)malloc(sizeof(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(Node** head_ref, int new_data)
{
/* allocate node */
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;
}
void printList(Node* n)
{
while (n) {
cout << n->data << " ";
n = n->next;
}
cout << endl;
}
struct Node* reverseList(struct Node* list)
{
Node *prev = NULL, *cur = list, *next = NULL;
while (cur != NULL) {
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
//----------------------------------------------------------------------------
Node* addTwoLists(Node* first, Node* second)
{
// code here
first = reverseList(first);
second = reverseList(second);
int carry = 0;
Node *head = NULL, *prev = NULL;
Node* sum = NULL;
// if any one of these is left we are stil left with addition
while (first != NULL or second != NULL or carry == 1)
{
int newVal = carry;
if (first)
newVal += first->data;
if (second)
newVal += second->data;
// to be used in the next node calculation
carry = newVal / 10;
newVal = newVal % 10;
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = newVal;
// appending in the beginning of the final ans list,
// this way we do not have to reverse in the end
newNode->next = sum;
sum = newNode;
// initialising nodes for next iteration
if (first)
first = first->next;
if (second)
second = second->next;
}
return sum;
}
//----------------------------------------------------------------------------
// { Driver Code Starts.
int main()
{
Node* first = NULL;
Node* second = NULL;
push(&first, 9);
push(&first, 8);
push(&first, 7);
push(&second, 1);
push(&second, 2);
push(&second, 3);
Node* ans = addTwoLists(first, second);
cout << "Sum is : ";
printList(ans);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C Code to add two nodes by reversing the two lists
#include <stdio.h>
#include <stdlib.h>
/* Linked list Node */
typedef struct Node {
int data;
struct Node* next;
} Node;
// Function to create a new node with given data
Node* newNode(int data)
{
Node* new_node = (Node*)malloc(sizeof(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(Node** head_ref, int new_data)
{
/* allocate node */
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;
}
void printList(Node* n)
{
while (n) {
printf("%d ", n->data);
n = n->next;
}
printf("\n");
}
Node* reverseList(Node* list)
{
Node *prev = NULL, *cur = list, *next = NULL;
while (cur != NULL) {
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
//----------------------------------------------------------------------------
Node* addTwoLists(Node* first, Node* second)
{
// code here
first = reverseList(first);
second = reverseList(second);
int carry = 0;
Node *head = NULL, *prev = NULL;
Node* sum = NULL;
while (first != NULL || second != NULL || carry == 1)
// if any one of these is left we are stil left with
// addition
{
int newVal = carry;
if (first)
newVal += first->data;
if (second)
newVal += second->data;
// to be used in the next node calculation
carry = newVal / 10;
newVal = newVal % 10;
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = newVal;
// appending in the beginning of the final ans list,
// this way we do not have to reverse in the end
newNode->next = sum;
sum = newNode;
// initialising nodes for next iteration
if (first)
first = first->next;
if (second)
second = second->next;
}
return sum;
}
//----------------------------------------------------------------------------
// { Driver Code Starts.
int main()
{
Node* first = NULL;
Node* second = NULL;
push(&first, 9);
push(&first, 8);
push(&first, 7);
push(&second, 1);
push(&second, 2);
push(&second, 3);
Node* ans = addTwoLists(first, second);
printf("Sum is : ");
printList(ans);
return 0;
}
Java
// Java program to add two numbers represented by Linked
// Lists by reversing lists
import java.util.*;
class LinkedList {
static Node head1, head2;
static class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
// function to reverse the linked list and return the head of the reversed list
static Node reverseList(Node list)
{
Node prev = null, curr = list, next = null;
while (curr != null)
{
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
// function that calculates and prints the sum of two numbers represented
// by linked lists
static void addTwoLists(Node first, Node second)
{
// code here
first = reverseList(first);
second = reverseList(second);
int carry = 0;
Node head = null, prev = null;
Node sum = null;
while (first != null || second != null || carry == 1) //if any one of these is left we are stil left with addition
{
int newVal = carry;
if (first!=null)
newVal += first.data;
if (second!=null)
newVal += second.data;
carry = newVal / 10; //to be used in the next node calculation
newVal = newVal % 10;
Node newNode = new Node(newVal);
newNode.next = sum; //appending in the beginning of the final ans list, this way we do not have to reverse in the end
sum = newNode;
if (first!=null) // initialising nodes for next iteration
first = first.next;
if (second!=null)
second = second.next;
}
printList(sum);
}
/* Utility function to print a linked list */
static void printList(Node head) {
while (head != null) {
System.out.print(head.data + " -> ");
head = head.next;
}
System.out.println("");
}
// Driver Code
public static void main(String[] args) {
LinkedList list = new LinkedList();
// creating first list
list.head1 = new Node(9);
list.head1.next = new Node(8);
list.head1.next.next = new Node(7);
System.out.print("First List : ");
list.printList(head1);
// creating second list
list.head2 = new Node(1);
list.head2.next = new Node(2);
list.head2.next.next = new Node(3);
System.out.print("Second List : ");
list.printList(head2);
System.out.print("Sum List : ");
// add the two lists and see the result
list.addTwoLists(head1, head2);
}
// this code is contributed by Abhijeet Kumar(abhijeet19403)
}
C#
// C# program to add two numbers represented by Linked
// Lists by reversing lists
using System;
using System.Collections.Generic;
public class List {
public class Node {
public int data;
public Node next;
public Node(int d) {
data = d;
next = null;
}
}
public static Node head1, head2;
// function to reverse the linked list and return the head of the reversed list
static Node reverseList(Node list)
{
Node prev = null, curr = list, next = null;
while (curr != null)
{
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
// function that calculates and prints the sum of two numbers represented
// by linked lists
static void addTwoLists(Node first, Node second)
{
// code here
first = reverseList(first);
second = reverseList(second);
int carry = 0;
Node sum = null;
//if any one of these is left we are stil left with addition
while (first != null || second != null || carry == 1)
{
int newVal = carry;
if (first!=null)
newVal += first.data;
if (second!=null)
newVal += second.data;
carry = newVal / 10; //to be used in the next node calculation
newVal = newVal % 10;
Node newNode = new Node(newVal);
newNode.next = sum;
//appending in the beginning of the final ans list,
//this way we do not have to reverse in the end
sum = newNode;
if (first!=null) // initialising nodes for next iteration
first = first.next;
if (second!=null)
second = second.next;
}
printList(sum);
}
/* Utility function to print a linked list */
static void printList(Node head) {
while (head != null) {
Console.Write(head.data + " -> ");
head = head.next;
}
Console.WriteLine("");
}
// Driver Code
public static void Main(String[] args) {
// creating first list
Node head1 = new Node(9);
head1.next = new Node(8);
head1.next.next = new Node(7);
Console.Write("First List : ");
printList(head1);
// creating second list
Node head2 = new Node(1);
head2.next = new Node(2);
head2.next.next = new Node(3);
Console.Write("Second List : ");
printList(head2);
Console.Write("Resultant List : ");
// add the two lists and see the result
addTwoLists(head1, head2);
}
}
// This code is contributed by Abhijeet Kumar(abhijeet19403)
Producción
Sum is : 1 1 1 0
Análisis de Complejidad:
Complejidad de tiempo: O(max(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(1)
Como constante se utiliza espacio extra.
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