264. Multiply Two Numbers Represented by Linked Lists

Two non-negative integers are each represented as a linked list of digits, most-significant digit first. Given both lists, print the digits of their product, most-significant digit first (no leading zeros, unless the product itself is 0).

Input: The first line contains an integer n1 followed by a line of n1 digits (most-significant first) for the first number. The next line contains an integer n2 followed by a line of n2 digits (most-significant first) for the second number. Output: Print the digits of the product, most-significant digit first, space-separated, with no leading zeros unless the product itself is 0.

1 <= number of digits in each list <= 500

The product of an n1-digit number and an n2-digit number always has AT MOST (n1+n2) digits - a useful bound to know when allocating space for the result.

Multiply two numbers, each given as a linked list of digits (most significant first), and print the product's digits. Brute force: Convert both numbers into standard fixed-size integer types and multiply directly - this fails for very large numbers (up to 500 digits each) that exceed what standard integer types can represent, requiring genuine big-number multiplication logic instead. Optimised: Implementing long multiplication manually (multiplying digit by digit and accumulating partial products with carries, exactly as taught for multi-digit multiplication by hand) correctly handles numbers of ARBITRARY size, limited only by available memory rather than a fixed integer type's range.

Treat multiplication as what it fundamentally means: repeatedly add the first number's value to an accumulator, once for every unit in the second number's value, using the linked-list addition procedure for each addition step. This is a correct reading of multiplication as repeated addition, but the number of additions needed equals the actual numeric value of one operand, which can be astronomically larger than its digit count, making this utterly infeasible for anything beyond tiny inputs. Time: O(value of one operand) Space: O(d1+d2)

Extract the digits of both lists into arrays, then multiply the way it's done by hand: for each digit of the second number, multiply it across every digit of the first number to produce a shifted partial product, and add that partial product into a running total. Convert the final accumulated digit array back into a linked list. This mirrors real long multiplication and is dramatically faster than repeated addition, though it performs a separate O(d1)-length addition pass for every digit of the second number to combine all the partial products. Time: O(d1*d2) Space: O(d1+d2)

Instead of forming and separately adding d2 shifted partial products, allocate one result array of size d1+d2 up front and directly accumulate every cross term result[i+j] += digit1[i] * digit2[j] into it as each product is computed, then do a single final left-to-right carry-propagation pass over the result array to normalize it into proper digits. This collapses the 'many partial products, each added separately' work of the better approach into one accumulation loop plus one carry pass, cutting overhead while keeping the same fundamental multiplication cost (going below this would require Karatsuba or FFT-based multiplication, unnecessary at these digit sizes). Time: O(d1*d2) Space: O(d1+d2)

1. Convert each linked list of digits into the actual number it represents, by walking it once and accumulating value = value*10 + digit. 2. Multiply the two resulting numbers using long multiplication (digit by digit, tracking carries) - the same fundamental technique used for the 'Add Two Numbers' problem's carry propagation, just for multiplication instead of addition. 3. Strip any leading zero digits from the final product before printing, unless the product is exactly 0.

Time: O(n1 * n2) - classic long multiplication's complexity, where n1 and n2 are the two numbers' digit counts. Space: O(n1 + n2), for the resulting product's digit representation.

either number being 0 (product is 0), single-digit numbers, and numbers up to 500 digits each requiring digit-by-digit multiplication without overflow.

Be ready to connect this directly to 'Add Two Numbers' - both problems require simulating manual arithmetic digit-by-digit specifically because the numbers may be far too large for standard fixed-size integer types.