Multiply two linked lists

GeeksforGeeks

Multiplying Linked Lists for Massive Numbers: Learn with O(max(n, m)) Time Complexity! ????

???? Problem:

Given two singly linked lists representing large numbers, the task is to multiply them. The result could be quite large, so we'll take modulo 109+710^9 + 7109+7.

?? Examples:

Input:

• LinkedList L1: 3 → 2
• LinkedList L2: 2
• Output: 64
• Explanation: Multiplying 32 by 2 gives 64.

Input:

• LinkedList L1: 1 → 0 → 0
• LinkedList L2: 1 → 0
• Output: 1000
• Explanation: Multiplying 100 by 10 gives 1000.

?? Approach:

In this problem, we need to simulate the process of multiplying two large numbers stored in linked lists, where each node represents a single digit. Here's how we can solve it efficiently.

Steps:

1. Step 1: Extract the numbers from both linked lists and convert them into their respective integer values.
2. Step 2: Multiply the two numbers.
3. Step 3: Return the product modulo 109+710^9 + 7109+7.

? Optimized Time Complexity: We achieve O(max(n, m)) time complexity by only traversing each list once to construct the numbers.

class Node 
{
int data;
Node next:

Node(int data)
{
this.data = data;
next = null;
}
}
class Solution
{
// Function to multiply two linked lists.
public long multiplyTwoLists(Node first, Node second)
{
long num1 = 0;
long num2 = 0;
long MOD = 1000000007;

// Extract first number from list L1
while(first != null)
{
num1 = (num1 * 10 + first.data)%M0D;
first = first.next;
}
// Extract second number from list L2
while(second != null)
{
num2 = (num2 * 10 + second.data) %MOD;
second = second.next;
}
// Multiply the two numbers and take modulo
return( num1 * num2 ) % MOD;
}
}        

?? Time Complexity:

• O(max(n, m)), where n is the number of nodes in list L1 and m in list L2.
• Auxiliary Space: O(1) (Constant space, as we’re not using any extra space apart from variables).

?? Summary:

This problem demonstrates how linked lists can be used to represent large numbers and how efficiently we can manipulate them by converting the list into integers, multiplying them, and using modular arithmetic to manage large results.