LinkedListProblem 32 of 36
Multiply 2 no. represented by LL
Multiply Two Numbers Represented by Linked Lists
Problem Statement
Given two numbers represented by linked lists, where each node contains a single digit, multiply the two numbers and return the result. The digits are stored in natural order (most significant digit first).
Example
Input:
List 1: 9 -> 4 -> 6 (represents 946)
List 2: 8 -> 4 (represents 84)
Output: 79464 (946 * 84 = 79464)
Can be represented as: 7 -> 9 -> 4 -> 6 -> 4
Brute Force Approach (Convert to Numbers)
Intuition
Convert both linked lists to numbers, multiply them, and optionally convert the result back to a linked list. This is straightforward but may overflow for very large numbers.
Algorithm
- Traverse first list and build the number
- Traverse second list and build the number
- Multiply the two numbers
- Return the result (or convert to linked list)
Code
java
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class MultiplyListsBrute {
static final long MOD = 1000000007;
public static long multiplyBruteForce(Node l1, Node l2) {
if (l1 == null || l2 == null) return 0;
long num1 = 0, num2 = 0;
// Convert first list to number
Node temp = l1;
while (temp != null) {
num1 = (num1 * 10 + temp.data) % MOD;
temp = temp.next;
}
// Convert second list to number
temp = l2;
while (temp != null) {
num2 = (num2 * 10 + temp.data) % MOD;
temp = temp.next;
}
// Multiply and return
return (num1 * num2) % MOD;
}
public static Node createList(String num) {
if (num.isEmpty()) return null;
Node head = new Node(num.charAt(0) - '0');
Node curr = head;
for (int i = 1; i < num.length(); i++) {
curr.next = new Node(num.charAt(i) - '0');
curr = curr.next;
}
return head;
}
public static void printList(Node head) {
while (head != null) {
System.out.print(head.data);
if (head.next != null) System.out.print(" -> ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
Node l1 = createList("946");
Node l2 = createList("84");
System.out.print("Number 1: ");
printList(l1);
System.out.print("Number 2: ");
printList(l2);
long result = multiplyBruteForce(l1, l2);
System.out.println("Product: " + result);
}
}Complexity Analysis
- Time Complexity: O(n + m) where n, m are lengths of the lists
- Space Complexity: O(1) - Only using constant extra space
Optimal Approach (Grade School Multiplication)
Intuition
For very large numbers that don't fit in standard data types, use grade-school multiplication algorithm. Multiply each digit with every other digit and accumulate results in an array.
Algorithm
- Reverse both lists for easier computation
- Create result array of size (n + m)
- For each pair of digits, multiply and add to appropriate position
- Handle carries
- Convert result array to linked list
Code
java
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class MultiplyListsOptimal {
public static Node reverse(Node head) {
Node prev = null;
Node curr = head;
while (curr != null) {
Node next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
public static int getLength(Node head) {
int len = 0;
while (head != null) {
len++;
head = head.next;
}
return len;
}
public static Node multiplyOptimal(Node l1, Node l2) {
if (l1 == null || l2 == null) return new Node(0);
int n = getLength(l1);
int m = getLength(l2);
// Reverse both lists
l1 = reverse(l1);
l2 = reverse(l2);
// Result array
int[] result = new int[n + m];
// Grade school multiplication
Node p1 = l1;
int i = 0;
while (p1 != null) {
Node p2 = l2;
int j = 0;
while (p2 != null) {
result[i + j] += p1.data * p2.data;
p2 = p2.next;
j++;
}
p1 = p1.next;
i++;
}
// Handle carries
int carry = 0;
for (int k = 0; k < result.length; k++) {
result[k] += carry;
carry = result[k] / 10;
result[k] %= 10;
}
// Find the actual end of result (skip leading zeros)
int end = result.length - 1;
while (end > 0 && result[end] == 0) {
end--;
}
// Create result linked list (in reverse order)
Node head = new Node(result[end]);
Node curr = head;
for (int k = end - 1; k >= 0; k--) {
curr.next = new Node(result[k]);
curr = curr.next;
}
return head;
}
public static void printList(Node head) {
while (head != null) {
System.out.print(head.data);
head = head.next;
}
System.out.println();
}
public static Node createList(String num) {
if (num.isEmpty()) return null;
Node head = new Node(num.charAt(0) - '0');
Node curr = head;
for (int i = 1; i < num.length(); i++) {
curr.next = new Node(num.charAt(i) - '0');
curr = curr.next;
}
return head;
}
public static void main(String[] args) {
Node l1 = createList("946");
Node l2 = createList("84");
System.out.print("Number 1: ");
printList(l1);
System.out.print("Number 2: ");
printList(l2);
Node result = multiplyOptimal(l1, l2);
System.out.print("Product: ");
printList(result);
}
}Complexity Analysis
- Time Complexity: O(n * m) where n, m are lengths of the lists
- Space Complexity: O(n + m) for the result array
Key Takeaways
- Two Approaches: Simple conversion vs grade-school multiplication
- Overflow Handling: Use modulo for simple approach, arrays for large numbers
- Grade-School Algorithm: Classic O(n*m) multiplication works digit by digit
- Reverse for Convenience: Reversing lists makes digit-position calculation easier
- Carry Management: Process carries after all multiplications
- Leading Zeros: Handle them when converting result back to list
- Big Integer: This is essentially implementing big integer multiplication
- Related Problems: Add two numbers represented by linked lists uses similar concepts