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:
Python3
# Python3 to multiply two numbers
# represented as Linked Lists
# Linked list node class
class Node:
# Function to initialize the node
def __init__(self, data):
self.data = data
self.next = None
# Linked List Class
class LinkedList:
# Function to initialize the
# LinkedList class.
def __init__(self):
# Initialize head as None
self.head = None
# Function to insert a node at the
# beginning of the Linked List
def push(self, new_data):
# Create a new Node
new_node = Node(new_data)
# Make next of the new Node
# as head
new_node.next = self.head
# Move the head to point to
# new Node
self.head = new_node
# Function to print the Linked
# List
def printList(self):
ptr = self.head
while (ptr != None):
print(ptr.data,
end = '')
if ptr.next != None:
print('->',
end = '')
ptr = ptr.next
print()
# Multiply contents of two Linked
# Lists
def multiplyTwoLists(first, second):
num1 = 0
num2 = 0
first_ptr = first.head
second_ptr = second.head
while first_ptr != None or second_ptr != None:
if first_ptr != None:
num1 = (num1 * 10) + first_ptr.data
first_ptr = first_ptr.next
if second_ptr != None:
num2 = (num2 * 10) + second_ptr.data
second_ptr = second_ptr.next
return num1 * num2
# Driver code
if __name__=='__main__':
first = LinkedList()
second = LinkedList()
# Create first Linked List 9->4->6
first.push(6)
first.push(4)
first.push(9)
# Printing first Linked List
print("First list is: ", end = '')
first.printList()
# Create second Linked List 8->4
second.push(4)
second.push(8)
# Printing second Linked List
print("Second List is: ",
end = '')
second.printList()
# Multiply two linked list and
# print the result
result = multiplyTwoLists(first,
second)
print("Result is: ", result)
# This code is contributed by kirtishsurangalikar
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