Sum two numbers stored digit by digit

Linked lists Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
a, b = [9, 9], [1]
carry, out = 0, []
for i in range(max(len(a), len(b))):
    total = carry
    total += a[i] if i < len(a) else 0
    total += b[i] if i < len(b) else 0
    out.append(total % 10)
    carry = total // 10
print(out, carry)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [0, 0] 1

Right: 99 + 1 leaves a carry that still needs its own digit.

That leftover carry is why the chain loop also runs while the carry is non-zero.

Why not the others?
  • B [0, 0, 1] 0. The loop stops before writing the final carry.
  • C [0, 1] 0. The carry passes through both digits.

30-second answer

Walk both chains together, adding the digits and a carry. Each step writes (total % 10) and keeps total // 10 as the carry. Continue while either chain has links or the carry is non-zero. O(max(n, m)) time; the output chain, O(max(n, m)) links, is the only extra memory.

Practise saying it · 45 s. No recording, just a timer

Explain adding digit chains.

Say your answer out loud, then check which of these points you covered:

  • Walk both together
  • total % 10 and carry
  • Keep going while carry

Deep dive

Lowest digit first is what makes one forward pass enough.

The final carry can add one extra digit (5 + 5 = 10).

If digits come highest first, turn both chains around first or use two stacks.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def add_digits(a: Link | None, b: Link | None) -> Link | None:
    front = Link(0)
    tail, carry = front, 0
    while a is not None or b is not None or carry:
        total = carry
        if a is not None:
            total, a = total + a.val, a.next
        if b is not None:
            total, b = total + b.val, b.next
        carry, digit = divmod(total, 10)
        tail.next = Link(digit)
        tail = tail.next
    return front.next

Common mistakes

  • Dropping the last carry.
  • Stopping when the shorter chain ends.

Senior take & follow-ups

Walk through 99 + 1 out loud; it covers carry and length change together.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if the digits are stored highest first?

    Show hint

    Push both onto stacks (or turn the chains around), add from the top, and build the result by adding links at the front.

  2. Why not convert to integers?

    Show hint

    In Python it works, but the question tests the carry logic, and other languages overflow.

What each operation costs: Linked List · Singly Linked List · Doubly Linked List

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.