add-two-numbers

Difficulty: Medium  ·  Topic: Linked List  ·  Practice it on parikshan: /practice/add-two-numbers/start

The story

A fintech reconciliation pipeline sums two streams of cents-precision amounts to produce a daily settlement total. The amounts are stored as arrays of decimal digits, least significant first, because the totals routinely exceed the safe range of a 64-bit integer once you accumulate a year of trading-desk volume in minor units. A signed 64-bit counter caps out near 9.2 quintillion units, which sounds like a lot until you remember a single desk can push trillions of cents-equivalents per day across a global book; double-precision floats lose cents above one quadrillion units. The fix is to store each operand as a digit array and add them with schoolbook column addition, propagating the carry digit by digit. That is the only representation that stays correct at arbitrary scale.

add-two-numbers is the textbook version. The choice to store digits reverse, so the head of each list is the units digit, is what makes the problem clean: schoolbook addition starts from the units column and propagates carries leftward, which matches the natural traversal direction of the linked lists. Without the reversal, you would need a second pass.

This is the Linked List cluster's bridge to carry-propagation arithmetic, which is closely related to plus-one.md from the Math / Matrix / Heap cluster.

What's actually being asked

You are given two non-negative integers as singly linked lists of decimal digits, least-significant-digit first. Return their sum as a linked list in the same format. Each input list has between 1 and 100,000 digits; no list has leading zeros except the literal 0.

For example, [2, 4, 3] represents 342 (digit at index 0 is 2, the units; index 1 is 4, the tens; index 2 is 3, the hundreds). The sum of [2, 4, 3] and [5, 6, 4] is 342 + 465 = 807, returned as [7, 0, 8].

The naive approach

Walk both lists, concatenate digits into Python ints (which natively handle arbitrary precision), add, decompose the result back into digits. Works in Python but defeats the purpose of the problem and fails in any language without big-integer support (C, Java without BigInteger, Rust, Go). The problem is here to teach carry propagation, the algorithm a real ALU would run.

A second naive: store the digits in arrays and add with column iteration. Correct, but copies the lists. The exam expects you to allocate only the output, not auxiliary buffers.

The key insight

Reversed storage is the gift. The head of each list is the units digit. Walk both lists in lockstep with one extra variable, the carry, which is always 0 or 1 (the sum of two digits plus a carry is at most 9 + 9 + 1 = 19, so the next carry is at most 1).

At each position:

• s = digit_a + digit_b + carry
• Append s % 10 to the output.
• Set carry = s // 10.

When one list runs out, treat its missing digit as 0. Crucially, do not stop the loop when both lists end if carry is still 1. A final carry produces one more output digit (e.g., 999 + 1 = 1000; three digits in, four digits out).

That last point is the bug AI agents commit most often on this problem. The loop condition has to be while a or b or carry, not while a and b.

Step-by-step approach

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def add_two_numbers(a, b):
    dummy = ListNode()
    tail = dummy
    carry = 0
    while a is not None or b is not None or carry:
        da = a.val if a is not None else 0
        db = b.val if b is not None else 0
        s = da + db + carry
        tail.next = ListNode(s % 10)
        tail = tail.next
        carry = s // 10
        if a is not None: a = a.next
        if b is not None: b = b.next
    return dummy.next

Loop invariant in English: every column up to and including the previous iteration has been correctly summed; carry holds any propagation from that column. When both inputs are exhausted and the carry is zero, no more columns to process.

The dummy head pattern is the Linked List primer's standard scaffold: it eliminates the "is this the first output digit?" special case. Return dummy.next.

Worked example

a = [2, 4, 3]       (represents 342)
b = [5, 6, 4]       (represents 465)

Output list: [7, 0, 8] representing 807. 342 + 465 = 807. ✓

Counter-case: a = [9, 9, 9] (999), b = [1] (1). Expected 1000, output [0, 0, 0, 1].

Output: [0, 0, 0, 1]. ✓ This is the case that exposes the while a or b or carry requirement. A loop condition of while a and b stops at iteration 1; while a or b stops at iteration 3 (the final 1 is lost).

Complexity

• Time: O(max(n1, n2)). One pass over the longer list, plus at most one extra iteration for the final carry.
• Space: O(max(n1, n2) + 1) for the output list. No auxiliary storage beyond a handful of variables.

The + 1 in space is the optional final carry digit. This matters in low-memory contexts: a fixed-buffer caller needs to allocate max(n1, n2) + 1 nodes, not just max(n1, n2).

Common pitfalls

1. Stopping the loop when both lists end, ignoring carry: the 999 + 1 = 1000 case. The loop condition must include or carry.
2. Skipping the dummy head: the first output digit becomes a special case, code branches, bugs creep in. The dummy is two lines.
3. Re-reading a.val after advancing a to null: easy to write da = a.val outside the null guard. The if a is not None else 0 ternary is the safe form.
4. Confusing reverse storage with most-significant-first: a [3, 4, 2] written intending "342" is wrong; the spec says least-significant first, so [3, 4, 2] is 243. Always read the spec.
5. Mutating the input lists: returning a fresh list (which this template does) is the safe contract. Some AI-generated versions splice into one of the input lists; if the caller still holds a reference, it now points into a Frankenstein list.

Where this shows up in the enterprise

• TigerBeetle financial ledgers: 128-bit account balances are stored as two 64-bit limbs added with carry; documented in the TigerBeetle design notes as the reason 64-bit balances were deprecated.
• Cryptocurrency wallets and Ethereum tooling: Ethereum's native integer width is 256 bits, well beyond any built-in numeric type, so every balance update inside ethers.js / web3.js / web3.py runs through BigNumber (or BigInt since EIP-2384), which is schoolbook arithmetic on digit arrays.
• OpenSSL / BoringSSL big-integer routines: every RSA / ECDSA signature involves modular addition that boils down to schoolbook-with-carry over digit arrays (called "limbs" in those codebases).
• GMP / MPIR libraries: the same algorithm at the core of arbitrary-precision arithmetic in Python (int), Mathematica, MATLAB, and most computer-algebra systems.
• Bignum arithmetic in language runtimes: CPython's PyLongObject, Java's BigInteger, JavaScript's BigInt, all store digits in fixed-base arrays and run this algorithm under the hood.
• Reconciliation pipelines at scale: as in the opening story; once cumulative daily totals across a global book exceed 2^63, integer overflow corrupts the books silently. Digit-array addition is the safe answer.
• Long-tail counters with arbitrary precision: any system where the accumulator must outlive the machine word width, e.g., scientific-instrument event counters running for years without rollover.

The fingerprint: arbitrary-precision arithmetic on a low-precision ALU, with operands streamed in least-significant-first order. Linked list is one way to store the digits; arrays are another. The carry-propagation algorithm is identical.

Variants you'll see elsewhere

• plus-one: array of digits, add one, propagate carry. Same algorithm, simpler operand. The Math cluster's analogue. This problem and plus-one should feel like the same problem.
• add-binary: binary strings, same carry idea with base 2.
• multiply-strings: long multiplication, decomposes into n shifted additions, each one this algorithm.
• add-two-numbers-ii: digits stored most-significant-first. Reverse both lists, run this algorithm, reverse the result. Composes with reverse-linked-list.
• add-strings: string version with no leading zeros. Same algorithm, different I/O.

The whole family is one algorithm wearing different costumes. Solve plus-one, then this, then add-binary, in sequence; the third one will write itself.

How parikshan turns this into a learning loop

Recommended sequence on parikshan:

1. Solve plus-one first (Math / Matrix / Heap cluster) to lock the carry algorithm without the linked-list complication.
2. Solve reverse-linked-list so you can later compose for the add-two-numbers-ii follow-up.
3. In practice mode on this problem, AI off, write the template. Run public tests.
4. The dynamic private tests will throw: 999 + 1, 0 + 0, lists of very different lengths, lists of length 100,000 with random digits, and the maximum carry case 999...9 + 1. The 999+1 family is where loops that ignore the trailing carry die.
5. Ask the parikshan assistant to Optimise. It will likely suggest pre-allocating an array of the right size; in linked-list land that is structurally the same as the dummy-head approach. The integrity penalty is small in practice mode; this is a fair use of the assistant.

In the AI-integrated workspace

Generated add-two-numbers code splits about 50/50: half the agents write the correct three-condition loop while a or b or carry, half write while a or b and miss the final carry. The bug passes every public test that does not end with a carry-out (which is most LeetCode samples). It fails the parikshan dynamic tests for the reason the test author chose: the worst-case carry chain.

Verification ritual on every agent-generated big-integer add:

1. Ask: "what is the loop condition?" The correct answer includes or carry.
2. Trace by hand on [9, 9, 9] + [1]. The expected output is [0, 0, 0, 1]. If the agent's code produces [0, 0, 0], the carry bug is present.
3. Read the output construction. Must be tail.next = ListNode(s % 10) followed by tail = tail.next. If only one of those lines is present, the output is malformed.

The broader skill being trained: carry propagation is universal. Anywhere bits or digits or limbs are combined under a base, the same algorithm applies. Recognising it across problems is what separates senior engineers from candidates who solve each instance from scratch. parikshan's Linked List cluster places this problem after plus-one for exactly this transfer.