Add Two Numbers

Big numbers that do not fit in 64 bits are often stored as sequences of digits. Adding them means doing what you learned in school: add column by column from the right, and carry a 1 when a column reaches 10. This problem stores each number as a linked list with the ones digit first, which turns out to be exactly the right order.

It is a good test of the "build a new list with a dummy and a tail" template, and of writing one loop that handles three separate ways of continuing: digits left in the first list, digits left in the second, or a carry left over.

The problem

You are given two non-empty lists. Each represents a non-negative integer, one digit per node, least significant digit first. Return their sum as a list in the same form.

• 9 → 9 → 1 (the number 199) and 7 → 3 (the number 37) → 6 → 3 → 2 (236).
• 5 and 5 → 0 → 1 (10). The sum has more digits than either input.
• 0 and 0 → 0.

Constraints: each list has 1 to 100 nodes; each node holds a digit 0–9; there are no leading zeros except for the number 0 itself.

Clarifying questions

• Which end holds the ones digit? The head. (If it were the tail, see the follow-ups.)
• Can the lists have different lengths? Yes.
• Can I modify the input lists? Assume you should not; build a new list for the result.
• Negative numbers? No.

Approach 1: convert to integers and back

Read each list into an integer, add them, and write the sum back out as a list.

1def add_two_numbers_convert(first: ListNode | None, second: ListNode | None) -> ListNode | None:2    """Turn each list into an int, add, turn back. Relies on Python's big ints."""3    def to_int(node: ListNode | None) -> int:4        number, place = 0, 15        while node is not None:6            number += node.value * place7            place *= 108            node = node.next9        return number1011    total = to_int(first) + to_int(second)12    dummy = ListNode()13    tail = dummy14    while True:15        tail.next = ListNode(total % 10)16        tail = tail.next17        total //= 1018        if total == 0:19            break20    return dummy.next

It works in Python, because Python integers grow without limit. It fails the problem everywhere else: a 100-digit number is far beyond the 64-bit maximum of about 1.8 × 10¹⁹ (20 digits), so in Java, C++ or Go it overflows silently. Even in Python it is not really O(n): each step on a big number touches all of its digits, so the conversion does roughly O(n²) digit work. The interviewer wants the digit-by-digit version, which works in any language.

The key insight

Column addition works from the least significant digit upward, carrying into the next column. The lists already store digits in that order. So walk both lists together, one column per step:

• total = carry + digit from first (if any) + digit from second (if any)
• the new digit is total % 10, and the new carry is total // 10 (always 0 or 1)

Keep going while either list has digits left or the carry is not zero. That one condition covers unequal lengths (one list keeps going after the other ends) and the final carry (5 + 5 needs an extra step to write the leading 1). A missing digit simply counts as 0.

Approach 2: digit by digit with a carry

1def add_two_numbers(first: ListNode | None, second: ListNode | None) -> ListNode | None:2    """Grade-school addition, one digit per step, least significant first."""3    dummy = ListNode()4    tail = dummy5    carry = 06    while first is not None or second is not None or carry:7        total = carry8        if first is not None:9            total += first.value10            first = first.next11        if second is not None:12            total += second.value13            second = second.next14        carry, digit = divmod(total, 10)15        tail.next = ListNode(digit)16        tail = tail.next17    return dummy.next

divmod(total, 10) returns the quotient and the remainder together: for 16 it gives (1, 6). The result is built with the dummy-and-tail template from the core lesson.

Dry run on 9 → 9 → 1 plus 7 → 3 (199 + 37):

After step 3 both lists are empty and the carry is 0, so the loop stops. 6 → 3 → 2 is 236. In step 3 the second list had already ended, and its missing digit counted as 0.

And 5 plus 5:

Step 2 runs only because of the or carry clause. Without it, the answer would be 0 instead of 0 → 1.

Time: O(max(m, n)) — one step per column, plus at most one step for a final carry. Space: O(max(m, n)) for the result list, which has at most one more digit than the longer input. Extra space beyond the output is O(1).

Edge cases

• Different lengths: handled inside the loop; a finished list contributes 0.
• A carry out of the last column: 5 + 5, or 9 → 9 + 1 = 0 → 0 → 1. The or carry clause adds the extra digit.
• Zero: 0 + 0 gives total 0 on step 1, writes 0, and stops. One node, correct.
• Long carry chains: 9 → 9 → 9 → 9 + 1 carries through every column. Each step still does constant work.

Follow-ups

• Digits stored most significant first (Add Two Numbers II): reverse both lists, run this function, and reverse the result — O(m + n) time. If you may not modify the inputs, push each list's digits onto a stack and pop them to add from the ones column; then insert each new digit at the front of the result.
• Subtract, or compare, two such numbers: the same column walk with a borrow instead of a carry; for comparison, check lengths first.
• Multiply two digit lists: the schoolbook method — every digit of one times every digit of the other, added into the right column. O(m · n).