102. Add 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 sum, most-significant digit first (no leading zeros, unless the sum 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 sum, most-significant digit first, space-separated, with no leading zeros unless the sum itself is 0.

1 <= number of digits in each list <= 10^4

A carry surviving past the very last (most-significant) digit pair - like 999 + 1 - adds ONE EXTRA leading digit to the result, an easy edge case to overlook if not explicitly handled.

Add two numbers, each written out digit by digit as a linked list (most significant digit first), and print the resulting sum's digits. Brute force: Convert each linked list into an actual large integer value, add them using built-in arbitrary-precision arithmetic, then convert the sum back into a list of digits - this can work but may not be practical if the number of digits (up to 10^4) exceeds what standard integer types can hold without special big-integer support. Optimised: Processing digit-by-digit from the least-significant end (after reversing) mirrors exactly how manual long addition works, correctly propagating carries one digit at a time - this handles arbitrarily large numbers of digits without ever needing a single number type large enough to hold the whole value at once.

Push every digit of each list onto its own stack while traversing left to right, so popping naturally yields digits least-significant-first. Repeatedly pop from both stacks, add the two digits plus carry, and push each resulting digit onto a third stack, then pop that stack to build the final list in correct most-significant-first order. This achieves the least-significant-first processing order the addition needs without ever physically reversing either input list. Time: O(n1+n2) Space: O(n1+n2)

Account for the length difference between the two lists (conceptually padding the shorter one with leading zeros), then recurse to the tail of both lists first and let each recursive call return the digit-sum node it created along with the carry it produced. Each parent call adds the carry it receives into its own digit sum before building its own node, so the carry naturally flows from the least significant digit back up to the most significant one purely through return values. This builds the result list directly in the correct order using only the recursion call stack, with no explicit stack or array of digits needed. Time: O(n1+n2) Space: O(max(n1,n2))

Reverse both linked lists so the least significant digit comes first, walk both reversed lists together adding corresponding digits plus carry (treating a missing digit as 0 once the shorter list runs out), and build the result in reverse order. Then reverse the result list back to most-significant-first order before returning it. This mirrors how addition is done by hand but requires three separate list reversals and temporarily disturbs the input lists' structure. Time: O(n1+n2) Space: O(max(n1,n2))

1. Reverse both digit lists (or use a stack for each) so you can process from the LEAST significant digit first, matching how manual addition actually works. 2. Walk both reversed sequences together, adding corresponding digits plus any carry from the previous step, recording the result digit and carrying over any overflow. 3. Reverse the resulting digit sequence back to most-significant-first order before printing, dropping any leading zero unless the whole result is zero.

Time: O(n1 + n2) - reversing both lists and adding digit-by-digit are both linear in the number of digits. Space: O(max(n1, n2)) for the resulting digit list (potentially one longer due to a final carry).

lists of very different lengths up to 10^4 digits each, a sum that produces an extra leading digit from a final carry, and a sum equal to exactly 0.

Be ready to mention that this same 'reverse, add with carry, reverse back' pattern extends directly to 'Add 1 to a Number Represented as a Linked List' (a special case where one 'number' is just 1) and to subtraction/multiplication variants.