The problem
Two non-negative numbers are stored as linked lists with digits in reverse order (ones digit first). Add them and return the sum as a list in the same format.
Input: 2 → 4 → 3 (342) and 5 → 6 → 4 (465) Output: 7 → 0 → 8 (807)
Picture it
Picture two trains where each coach is one digit, ones digit at the front, like an odometer read backwards. Just like adding on paper, we add the two front digits plus any carry, write the last digit of that sum on a new coach, and carry the tens to the next column. If a carry is left at the end, it becomes one more coach.
How to recognise it
- Two numbers arrive as digit lists, and the digits are stored ones digit first. That is exactly the order in which you add numbers on paper, right to left.
- The numbers can be longer than any built-in integer type (LeetCode allows 100 digits), so converting to an integer is not safe in most languages.
- The answer is a new list in the same format, so you build it one node per column, using a dummy node to avoid a special case for the first digit.
- Anything that says "add digit by digit with a carry" (big-number strings, binary strings) is the same column addition.
Start with brute force
Turn each list into an integer, add the integers, and turn the sum back into a list.
def add_brute(l1, l2):
def to_int(node):
num, place = 0, 1
while node:
num += node.val * place
place *= 10
node = node.next
return num
total = to_int(l1) + to_int(l2)
dummy = tail = Node(0)
while True:
total, digit = divmod(total, 10)
tail.next = Node(digit)
tail = tail.next
if total == 0:
return dummy.next
In Python this works and is fast enough for 100 digits, because Python integers have no size limit. In Java or C++ a 64-bit integer holds only about 19 digits, so a 100-digit number overflows. The problem is designed so you add the digits yourself.
From brute force to the idea
- Find the waste. Converting builds a huge number only to break it apart again. The lists already give you the digits in the order you need them.
- Add one column at a time. Walk both lists together. For each column,
s = carry + digit from l1 + digit from l2, using 0 for a list that has already ended. - Split the column sum.
divmod(s, 10)gives the new carry (0 or 1) and the digit to write. The largest column sum is 9 + 9 + 1 = 19, so the carry never exceeds 1. - Append to the result. A dummy node means every digit is added the same way:
tail.next = Node(digit), then movetail. - Keep going while anything is left. The loop runs
while l1 or l2 or carry. Thecarrypart adds a final 1 when the last column overflows, as in 5 + 5 = 10.
This is the key idea: school column addition, walking both lists at once and carrying into the next node.
The key idea
Column addition walking both lists at once, carrying as you go. O(max(m, n)).
Python solution
def add(l1, l2): # digits stored backwards
dummy = tail = Node(0)
carry = 0
while l1 or l2 or carry:
s = carry + (l1.val if l1 else 0) + (l2.val if l2 else 0)
carry, digit = divmod(s, 10)
tail.next = Node(digit)
tail = tail.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.nextIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(m + n) loop steps, but each big-integer operation grows with the number, so up to O((m + n)²) digit work | O(max(m, n)) for the result, plus the big integers |
| Column addition (shown code) | O(max(m, n)): one loop step per column, plus at most one for the final carry | O(max(m, n)) for the result list; O(1) besides it |
Edge cases
- Different lengths (
9 → 9 → 9 → 9plus9 → 9, 9,999 + 99): missing digits count as 0, giving8 → 9 → 0 → 0 → 1(10,098). - Final carry (
5plus5): the loop runs once more for the carry and returns0 → 1. - Both zero (
0plus0): returns a single0node, not an empty list. - Carry through a long run (
9 → 9 → 9plus1): returns0 → 0 → 0 → 1. - The inputs are not changed: the shown code only reads them and creates new nodes.
Common mistakes
- Looping
while l1 and l2, which stops at the end of the shorter number and drops the rest. - Leaving
or carryout of the loop condition, so 5 + 5 returns0instead of0 → 1. - Setting
carry = 1whens >= 10but never back to 0 whens < 10. The carry is then added to every later column, and withor carryin the condition the loop never ends. - Reading
l1.valwithout checking thatl1exists, which raisesAttributeErroronce the shorter list ends.
The same task, but each list stores its digits most significant first: 7 → 2 → 4 → 3 (7,243) plus 5 → 6 → 4 (564) gives 7 → 8 → 0 → 7 (7,807). Do not reverse the input lists. Describe your approach, then write it if you like.
Compare with our answer
Addition must still start at the ones digit, which is now at the end. Push each list's digits onto a stack, then pop from both: the stacks give the digits right to left. Each new digit belongs in front of the ones already written, so build the result by prepending.
def add_forward(l1, l2):
s1, s2 = [], []
while l1:
s1.append(l1.val)
l1 = l1.next
while l2:
s2.append(l2.val)
l2 = l2.next
head, carry = None, 0
while s1 or s2 or carry:
s = carry + (s1.pop() if s1 else 0) + (s2.pop() if s2 else 0)
carry, digit = divmod(s, 10)
head = Node(digit, head) # prepend: we work right to left
return head
Time O(m + n), space O(m + n) for the stacks.
A strong answer mentions: why the ones digit must come first, stacks (or reversing) to get that order, prepending new digits, and the final carry.
1. Two non-negative numbers of up to 10^5 digits arrive as strings, in a language without big integers. Which approach fits best?
Column addition never stores more than one digit's worth of carry, so length does not matter. 64-bit integers overflow after about 19 digits, and doubles keep only about 15 to 17 significant digits, so the low digits would be wrong.
2. Why does the shown code run in O(max(m, n)) time rather than O(m · n)?
One iteration per column, plus at most one for a final carry, is O(max(m, n)). Pairing every digit with every other digit is what multiplication needs, not addition.
3. A learner changes the loop to while l1 or l2:. Which input now gives a wrong answer?
99 + 1 = 100: the last column leaves a carry of 1, but both lists have ended, so the loop stops and returns 0 → 0. In 342 + 465 the carry happens in the middle column, where the loop still continues.
Score 60% or more and the lesson is marked complete.