Dados dos números representados por listas enlazadas, escribe una función que devuelva la multiplicación de estas dos listas enlazadas.
Ejemplos:
Input: 9->4->6
8->4
Output: 79464
Input: 3->2->1
1->2
Output: 3852
Solución :
recorra ambas listas y genere los números necesarios para multiplicar y luego devuelva los valores multiplicados de los dos números.
Algoritmo para generar el número a partir de la representación de lista enlazada:
1) Initialize a variable to zero 2) Start traversing the linked list 3) Add the value of the first node to this variable 4) From the second node, multiply the variable by 10 and also take the modulus of this value by 10^9+7 and then add the value of the node to this variable. 5) Repeat step 4 until we reach the last node of the list.
Utilice el algoritmo anterior con ambas listas vinculadas para generar los números.
A continuación se muestra el programa para multiplicar dos números representados como listas enlazadas:
C++
// C++ program to Multiply two numbers
// represented as linked lists
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
// 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 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;
}
// Multiply contents of two linked lists
long long multiplyTwoLists (Node* first,
Node* second)
{
long long N= 1000000007;
long long num1 = 0, num2 = 0;
while (first || second)
{
if(first)
{
num1 = (((num1) * 10) % N +
first -> data);
first = first -> next;
}
if(second)
{
num2 = (((num2) * 10) % N +
second -> data);
second = second->next;
}
}
return (((num1 % N) *
(num2 % N)) % N);
}
// A utility function to print a
// linked list
void printList(struct Node *node)
{
while(node != NULL)
{
cout << node -> data;
if(node -> next)
cout << "->";
node = node -> next;
}
cout << "";
}
// Driver code
int main()
{
struct Node* first = NULL;
struct Node* second = NULL;
// Create first list 9->4->6
push(&first, 6);
push(&first, 4);
push(&first, 9);
printf("First List is: ");
printList(first);
// Create second list 8->4
push(&second, 4);
push(&second, 8);
printf("Second List is: ");
printList(second);
// Multiply the two lists and see result
cout << "Result is: ";
cout << multiplyTwoLists(first,
second);
return 0;
}
Producción:
First List is: 9->4->6 Second List is: 8->4 Result is: 79464
Complejidad de tiempo: O(max(n1, n2)), donde n1 y n2 representan el número de Nodes presentes en la primera y segunda lista enlazada respectivamente.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
Consulte el artículo completo sobre Multiplicar dos números representados por listas enlazadas para obtener 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