Problem statement

Each of the two singly linked lists first and second holds the decimal digits of a non-negative number, most significant digit first (leading zeros are possible). The numbers can be far too large for any integer type.

Return the product of the two numbers modulo 10^9 + 7.

Example 1

Input: first = [3,2], second = [2]
Output: 64
Explanation: 32 × 2 = 64.

Example 2

Input: first = [1,0,0], second = [1,0]
Output: 1000
Explanation: 100 × 10 = 1000.

Example 3

Input: first = [9,9,9,9,9,9,9,9,9,9], second = [9,9]
Output: 999992978
Explanation: 9,999,999,999 × 99 = 989,999,999,901, which leaves 999,992,978 modulo 10^9 + 7.

Constraints

• 1 <= number of nodes in each list <= 100
• 0 <= Node.val <= 9

Hints for Multiply Two Linked Lists

1. Hint 1

   A 100-digit number does not fit any built-in integer — but you only need its value modulo 10^9 + 7.

2. Hint 2

   Read a number digit by digit with x = x * 10 + digit, reducing modulo 10^9 + 7 after every step.

3. Hint 3

   Multiply the two reduced values and reduce again. The product of two values below 10^9 + 7 needs 64-bit arithmetic.

How to solve Multiply Two Linked Lists

Taking remainders commutes with addition and multiplication, so each list can be folded into its value modulo M = 10^9 + 7 with Horner's rule, and the product of those two remainders, reduced once more, is the answer.

Approach

1. Fold the first list: x = (x * 10 + digit) mod M for each node.
2. Fold the second list the same way into y.
3. Return (x * y) mod M, computing the product in 64-bit arithmetic.

Why it works

(a * 10 + d) mod M = ((a mod M) * 10 + d) mod M and (x * y) mod M = ((x mod M) * (y mod M)) mod M, so reducing at every step never changes the final remainder while keeping every intermediate below M * 10 + 9 and M².

Complexity

• Time — O(n + m)
• Space — O(1)

Pitfalls

• x * y can reach about 10^18 — use a 64-bit type (and in JavaScript, split the multiplication or use BigInt: a double loses the low digits).
• Reduce while folding, not only at the end — the number itself overflows after a few digits.
• Leading zeros are ordinary digits; Horner's rule handles them.

Reference solution

Python

from typing import Optional

def multiplyTwoLists(first: Optional[ListNode], second: Optional[ListNode]) -> int:
    MOD = 1000000007

    def fold(node):
        x = 0
        while node:
            x = (x * 10 + node.val) % MOD
            node = node.next
        return x

    return fold(first) * fold(second) % MOD

Java

public static int multiplyTwoLists(ListNode first, ListNode second) {
    final long MOD = 1000000007L;
    long a = 0, b = 0;
    for (ListNode node = first; node != null; node = node.next) a = (a * 10 + node.val) % MOD;
    for (ListNode node = second; node != null; node = node.next) b = (b * 10 + node.val) % MOD;
    return (int) (a * b % MOD);
}

C++

int multiplyTwoLists(ListNode* first, ListNode* second) {
    const long long MOD = 1000000007LL;
    long long a = 0, b = 0;
    for (ListNode* node = first; node; node = node->next) a = (a * 10 + node->val) % MOD;
    for (ListNode* node = second; node; node = node->next) b = (b * 10 + node->val) % MOD;
    return (int) (a * b % MOD);
}

JavaScript

var multiplyTwoLists = function(first, second) {
    var MOD = 1000000007;
    var fold = function(node) {
        var x = 0;
        for (; node !== null; node = node.next) x = (x * 10 + node.val) % MOD;
        return x;
    };
    var a = fold(first), b = fold(second);
    // a * b can reach 10^18, beyond a double's 2^53: split b into 16-bit halves.
    var hi = Math.floor(b / 65536), lo = b % 65536;
    return ((a * hi) % MOD * 65536 + a * lo) % MOD;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Convert Binary Number in a Linked List to Integer Easy
• Check if Any Element Has Prime Frequency Easy
• Convert Date to Binary Easy
• Count Ways to Tile a 2 x N Floor Easy
• Find Nth Root of M Easy
• Valid Boomerang Easy