Multiply two linked lists

JavaView on GFG

Time: O(n+m)

Space: O(1)

Intuition

Multiply two numbers represented as linked lists. Build numbers modulo 10^9+7.

Algorithm

1Traverse each list: num = (num*10 + digit) % MOD. Multiply both modular values.

Common Pitfalls

•Use modular arithmetic throughout to avoid overflow. Result = (num1 * num2) % MOD.

Multiply two linked lists.java

Java

// Approach: Traverse both lists to compute their numeric values (mod 10^9+7), then multiply.
// Time: O(n+m) Space: O(1)
class Solution {
    long e = 1000000007;

    public long multiplyTwoLists(Node first, Node second) {
        long sum1 = 0, sum2 = 0;

        while (first != null) {
            sum1 = ((sum1 * 10) + first.data) % e;
            first = first.next;
        }

        while (second != null) {
            sum2 = ((sum2 * 10) + second.data) % e;
            second = second.next;
        }

        return (sum1 * sum2) % e;
    }
}

Was this solution helpful?