Log inSign up
mediumGeeksforGeeksNot Started

Multiply Two Numbers Represented by Linked Lists

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on GeeksforGeeks
Lesson

Problem Statement

Given elements of two linked lists list1 and list2 representing two non-negative integers, your task is to multiply these two numbers and return the product modulo 10^9 + 7 (1000000007).

The digits are stored such that the most significant digit is at the head of the list.

Example 1 · Example 1:

Input: first = 3 -> 2, second = 2
Output: 64
Explanation: 32 * 2 = 64. 64 % 1000000007 = 64.

Example 2 · Example 2:

Input: first = 1 -> 0 -> 0, second = 1 -> 0
Output: 1000
Explanation: 100 * 10 = 1000.

Constraints:

  • 1 <= size of list1, list2 <= 10^5
  • 0 <= Node.val <= 9

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Apply Horner's rule for polynomial number accumulation on forward-ordered linked lists.
  • Utilize modular arithmetic identities to avoid 64-bit integer overflow.
  • Achieve linear O(N + M) complexity and O(1) space.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Multiplying large numbers stored as linked lists.
  • Most-significant-digit at the head node.
  • Result requested modulo 109 + 7.

Algorithmic Decision Tree:

  • Use modulo accumulation (num * 10 + val) % MOD at every step to prevent integer overflow.
  • Use 64-bit integer types (long long in C++, long in Java, BigInt in JS) during the final multiplication.

Connected Patterns:

Add Two NumbersAdd Two Numbers IIMultiply Strings

1. Brute Force — String Concatenation & BigInt Multiplication

Intuition

Traverse both lists and accumulate all digits into strings. Multiply the strings using BigInteger or BigInt and take modulo 109 + 7.

Algorithm

  1. Step 1: Traverse list1 and append digits to string s1.
  2. Step 2: Traverse list2 and append digits to string s2.
  3. Step 3: Multiply BigInts: (BigInt(s1) * BigInt(s2)) % 1000000007n.
  4. Step 4: Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4using namespace std;
5
6struct Node {
7 int data;
8 Node* next;
9 Node(int x) : data(x), next(nullptr) {}
10};
11
12class Solution {
13public:
14 long long multiplyTwoLists(Node* first, Node* second) {
15 long long MOD = 1000000007;
16 string s1 = "", s2 = "";
17 for (Node* c = first; c; c = c->next) s1 += to_string(c->data);
18 for (Node* c = second; c; c = c->next) s2 += to_string(c->data);
19
20 long long n1 = 0, n2 = 0;
21 for (char ch : s1) n1 = (n1 * 10 + (ch - '0')) % MOD;
22 for (char ch : s2) n2 = (n2 * 10 + (ch - '0')) % MOD;
23
24 return (n1 * n2) % MOD;
25 }
26};
27
28int main() {
29 Node* l1 = new Node(3);
30 l1->next = new Node(2);
31 Node* l2 = new Node(2);
32
33 Solution sol;
34 cout << "Brute Force Multiply: " << sol.multiplyTwoLists(l1, l2) << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(N + M) — Builds strings of length N and M, then performs BigInt multiplication and modulo.
  • Space complexity: O(N + M) — Allocates memory for digit strings and BigInt representations.

Why Brute Force Doesn't Scale:

Grade-school multiplication takes O(N * M) time, which for N, M = 105 requires 1010 operations (>10 seconds).

For N = 100,000 and M = 100,000, Horner's rule completes in <0.8ms.

2. Better — Array Vector Horner's Accumulator

Intuition

Collect node digit values into arrays, then apply modular polynomial evaluation over the arrays.

Algorithm

  1. Step 1: Extract digits from first into array a1.
  2. Step 2: Extract digits from second into array a2.
  3. Step 3: n1 = 0; for each d in a1: n1 = (n1 * 10 + d) % MOD.
  4. Step 4: n2 = 0; for each d in a2: n2 = (n2 * 10 + d) % MOD.
  5. Step 5: Return (n1 * n2) % MOD.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6struct Node {
7 int data;
8 Node* next;
9 Node(int x) : data(x), next(nullptr) {}
10};
11
12class Solution {
13public:
14 long long multiplyTwoLists(Node* first, Node* second) {
15 long long MOD = 1000000007;
16 vector<int> a1, a2;
17 for (Node* c = first; c; c = c->next) a1.push_back(c->data);
18 for (Node* c = second; c; c = c->next) a2.push_back(c->data);
19
20 long long n1 = 0, n2 = 0;
21 for (int d : a1) n1 = (n1 * 10 + d) % MOD;
22 for (int d : a2) n2 = (n2 * 10 + d) % MOD;
23
24 return (n1 * n2) % MOD;
25 }
26};
27
28int main() {
29 Node* l1 = new Node(3);
30 l1->next = new Node(2);
31 Node* l2 = new Node(2);
32
33 Solution sol;
34 cout << "Better Array Horner: " << sol.multiplyTwoLists(l1, l2) << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(N + M) — Extracts digits into arrays in O(N + M), then applies Horner's rule on the arrays.
  • Space complexity: O(N + M) — Allocates two auxiliary arrays for digit lists.

3. Optimal — Single-Pass In-Place Horner's Modular Accumulation

Intuition

Traverse first directly, updating num1 = (num1 * 10 + first.data) % MOD at every node. Traverse second directly, updating num2 = (num2 * 10 + second.data) % MOD. Return (num1 * num2) % MOD using 64-bit integer multiplication to avoid overflow.

Algorithm

  1. Step 1: Set MOD = 1000000007, num1 = 0, num2 = 0.
  2. Step 2: While first != null: num1 = (num1 * 10 + first.data) % MOD, first = first.next.
  3. Step 3: While second != null: num2 = (num2 * 10 + second.data) % MOD, second = second.next.
  4. Step 4: Return (num1 * num2) % MOD.

Multiply Two Linked Lists Master Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
num1 = 100
Visual state
Values and pointers at this exact step
linked list
num1 → 100
Node 1
1
Node 0a
0
Node 0b
0
NULL
Why this step matters

num1 = 100.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct Node {
6 int data;
7 Node* next;
8 Node(int x) : data(x), next(nullptr) {}
9};
10
11class Solution {
12public:
13 long long multiplyTwoLists(Node* first, Node* second) {
14 long long MOD = 1000000007;
15 long long num1 = 0;
16 long long num2 = 0;
17
18 while (first != nullptr) {
19 num1 = (num1 * 10 + first->data) % MOD;
20 first = first->next;
21 }
22
23 while (second != nullptr) {
24 num2 = (num2 * 10 + second->data) % MOD;
25 second = second->next;
26 }
27
28 return (num1 * num2) % MOD;
29 }
30};
31
32int main() {
33 Node* l1 = new Node(3);
34 l1->next = new Node(2);
35 Node* l2 = new Node(2);
36
37 Solution sol;
38 cout << "Optimal In-Place Multiply: " << sol.multiplyTwoLists(l1, l2) << endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(N + M) — Visits each node of first (N) and second (M) exactly once. Constant number of arithmetic operations per node.
  • Space complexity: O(1) — Operates strictly in-place using O(1) integer variables.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — String Concatenation & BigInteger MultiplicationO(N + M)O(N + M)Convert both linked lists into strings of digits. Parse as arbitrary precision BigInteger objects, multiply them, and compute modulo 10^9 + 7.Memory allocation for digit strings.
2.Better — Reverse Lists & Column-by-Column Grade-School MultiplicationO(N * M)O(N + M)Reverse both lists so digits are least-significant first. Simulate full manual grade-school multiplication digit-by-digit.O(N * M) quadratic runtime.
3.Optimal — Single-Pass Horner's Modular AccumulationOptimalO(N + M)O(1)Evaluate num1 = (num1 * 10 + node.val) % MOD across list1, and num2 = (num2 * 10 + node.val) % MOD across list2 in a single linear pass. Return (num1 * num2) % MOD.Optimal.

Common Pitfalls & Crucial Edge Cases

Integer overflow before modulo

Multiplying two 32-bit signed ints (num1 * num2) when each is up to 10^9 can result in 10^18, which overflows a 32-bit integer. Must use 64-bit long long in C++ / long in Java / BigInt in JS.

Applying modulo only at the end

Trying to accumulate the full integer without modulo will quickly overflow even 64-bit integers on lists with >19 digits.

Crucial Edge Cases to Validate:

  • Single Digits — first = 0, second = 5 -> (0 * 5) % MOD = 0.
  • Large Digits (10^5 digits) — Modulo arithmetic at each step keeps intermediate values < 109 + 7, preventing 64-bit integer overflow.
  • Equal Numbers — first = 10, second = 10 -> 100.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the modular identity clearly: 'We accumulate each number modulo 109 + 7 on the fly using Horner's method.'
  2. Point out the 64-bit data type requirement to avoid intermediate overflow during num1 * num2.
  3. Mention that forward traversal (MSD first) matches natural Horner evaluation without requiring list reversals.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does (num * 10 + digit) % MOD accurately preserve the value under modular arithmetic?

2.What integer type is required in C++ and Java when computing (num1 * num2) % 1000000007?

3.What is the time and space complexity of the optimal Horner's rule approach?

Back to DSA Sheet