Digit-by-digit with carry

37 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Add 342 and 465 the way you learned in school: write them one above the other, start from the units column. 2 + 5 = 7, write 7. 4 + 6 = 10, write 0, carry 1. 3 + 4 + 1 = 8, write 8. Answer 807.

Now the numbers are given as linked lists, each box one digit, least significant digit first: 2 → 4 → 3 and 5 → 6 → 4. That is exactly the order school addition walks the digits, so the lists are already set up for the column method.

The by-hand method is already the right algorithm. What is left is to do it without converting to real numbers, because the lists might be a thousand digits long and no integer type holds that. The only state you carried from column to column was a single carry digit, 0 or 1. That is all the memory the algorithm needs.

Build the structure, one piece at a time

Piece 1: two walkers. One pointer on each list, starting at the first box (the units digit).

Piece 2: a carry. One number, starting at 0.

Piece 3: the column step. Take the digit under each walker (0 if that list has run out), add them and the carry. The new digit is the sum mod 10; the new carry is the sum ÷ 10 (0 or 1). Append the new digit to the result list and advance both walkers.

Piece 4: the stop rule. Keep going while either list has boxes left or the carry is 1. The last condition is what turns 999 + 1 into 1000: after the three columns, the carry is 1 and a fourth box must be written.

Result list: 7 → 0 → 8, which reads as 807. Building the result uses a dummy head and a tail pointer, so the first digit needs no special case.

Why it is correct

The invariant: after k columns, the result list holds the lowest k digits of the true sum, and carry equals the amount still owed to column k + 1.

This is the column method's own correctness argument, made precise. The true sum's lowest k digits depend only on the lowest k digits of the inputs and the carries between them. Each step computes digit and carry from exactly those, so by induction each written digit is right. The carry can never exceed 1:

sum ≤ 9 + 9 + 1 = 19, so carry = ⌊sum / 10⌋ ≤ 1

The stop rule guarantees nothing is left owed: the loop ends only when both lists are exhausted and the carry is 0.

For multiplication of digit strings the same structure applies with a wider carry: the product of digit i and digit j is added into position i + j of a result array, and one final pass normalises each position to a single digit, carrying the excess upward.

Why it is fast

Each column is a constant amount of work, and the number of columns is the length of the longer list, plus one for a final carry.

time = O(max(n, m)), memory for the result = O(max(n, m)), working memory = one carry

A thousand-digit number is a thousand columns, no big-integer library needed.

How to recognise it in an interview

The cues are "add two numbers represented as", "plus one", "add binary strings", "multiply strings", digits stored in a list or string, and lengths that rule out converting to an integer. Say: "I walk both inputs from the least significant end with a carry, writing one digit per position, and keep going while a carry remains."

Add Two Numbers is the example above. Add Binary is the same with base 2, so digit = sum mod 2 and carry = sum ÷ 2. Plus One is the special case where the second number is 1 and the loop usually stops after the first column. When the digits are stored most significant first, reverse the lists first or use two stacks to walk them from the end.

02The idea in one line

Walk both lists, add digits plus carry, emit one node per position.

Reach for it when: Add two numbers, plus one, add binary/strings, multiply strings.

Cost: O(max(n,m)) time.

03The walk-through, step by step

The video works one example: Add Two Numbers 342 + 465 as 2→4→3 and 5→6→4. These are its captions in order, so you can follow without the video or check a step you missed.

1. Walk both lists together; each position emits (a + b + carry) mod 10
2. 2 + 5 + carry 0 = 7
3. Write digit 7, carry = 0
4. 4 + 6 + carry 0 = 10
5. Write digit 0, carry = 1
6. 3 + 4 + carry 1 = 8
7. Write digit 8, carry = 0
8. Lists ended and carry is 0: nothing more to write
9. Result 7→0→8 reads as 807 = 342 + 465
10. One node per position: O(max(n, m))

04Asked at Google

8 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Linked List: Fast and slow pointers, In-place reversal, Dummy head and splice, Clone with a map or interleaving.