Add Two Numbers
Two non-empty lists store digits in reverse order, one digit per node. Add the numbers and return the sum as a list, also in reverse order.
- The number of nodes in each linked list is in the range [1, 100].
- 0 <= Node.val <= 9
- It is guaranteed that the list represents a number that does not have leading zeros.
Intuition
Add two numbers adds two integers stored as linked lists whose digits run in reverse order, returning the sum in the same form. The reversal is a gift rather than an obstacle — least significant digit first is exactly the order manual addition works in.
So the algorithm is column addition, walked node by node:
- At each position add the two digits and the carry, store sum % 10 in a new node, and keep sum / 10 as the next carry.
No reversal, no conversion to integers. Converting is in fact the trap: the lists can hold up to 100 digits, which overflows every fixed-width integer type. The linked list representation exists precisely to allow arbitrarily large numbers, so the digit-wise walk is the intended approach rather than a workaround.
The lists can differ in length, so the loop must continue while either list has nodes remaining, treating a missing digit as 0. Stopping when the shorter list ends silently truncates the answer.
The case most often missed is a final carry. Adding [5] and [5] produces a carry after both lists are exhausted, and the answer needs an extra node. So the loop condition must also continue while the carry is non-zero, or 999 + 1 returns 000.
A dummy head node removes the special case for the first node. Build onto dummy.next and return that at the end, so no branch is needed to distinguish the first append from the rest.
To add two numbers in linked list form, digits stored least-significant-first means you can add left to right exactly as you would on paper. The dummy head removes the special case for the first node, and driving the loop on l1 or l2 or carry folds three termination cases — unequal lengths and a final carry — into one condition.
Approach
Before reading on: price up what the direct approach costs here, then ask which pointers must be saved before you overwrite anything. Aim for O(max(m, n)) time and O(max(m, n)) space.
Use the reversed order directly
Least significant digit first is the order manual addition already uses. No reversal is needed — walk both lists forward and add column by column.
Never convert to an integer
The lists hold up to 100 digits, which overflows every fixed-width type. The linked list representation exists to allow numbers too large to store, so digit-wise addition is the intended method.
Add digits with a carry
At each position compute d1 + d2 + carry, store sum % 10 in a new node, and set carry = sum / 10. This is column addition, one node per column.
Continue while either list remains
The lists can differ in length, so loop while either has nodes, treating a missing digit as 0. Stopping at the shorter list truncates the answer.
Handle the final carry
Continue while the carry is non-zero too. Adding [5] and [5] carries after both lists end, and without this 999 + 1 returns 000.
Build behind a dummy head
Append onto a dummy node and return dummy.next. This removes the branch that would otherwise distinguish the first node from every later one.
Cost of the traversal
Each list is walked once, giving O(max(m, n)) time. The output list is the same length plus at most one carry node, so space is O(max(m, n)).
Solution & live demo
Common pitfalls
Dropping the final carry
while l1 or l2:
while l1 or l2 or carry:
Adding 5 + 5 leaves a carry after both lists are exhausted, and the answer needs one more node. Including carry in the loop condition handles it without a trailing special case.
Advancing pointers without a null check
l1 = l1.next l2 = l2.next
l1 = l1.next if l1 else None l2 = l2.next if l2 else None
The lists can differ in length, so one runs out first and dereferencing it throws. The same guard is needed when reading the values — hence a = l1.val if l1 else 0.
Building the number then converting back
n1 = int(''.join(str(d) for d in digits1)[::-1])
return make_list(n1 + n2)carry, digit = divmod(a + b + carry, 10)
Works in Python's arbitrary-precision integers, but overflows immediately in C++ or Java — and the lists can hold 100 digits. Digit-wise addition has no size limit and is what the question is testing.
Edge cases
Treat a missing node as 0, so the shorter list simply contributes zeros once exhausted.
The loop condition includes carry, so a trailing carry creates the extra high-order node.
0 + 0 = 0 with no carry; one result node holding 0 is produced.