Add numbers digit by digit
Add two numbers stored as chains of digits, least significant first, carrying as you go and building the answer chain on the fly. About 14 minutes.
Column addition on a chain
Each chain holds a number with the units digit first. So 2, 4, 3 means 342. Adding the numbers is the school method: add the units, write the last digit, carry the rest, then move to the tens.
At each column, the sum is the digit from the first chain, the digit from the second chain, and the carry. A chain that has run out counts as a zero. The new digit, the sum modulo 10, becomes the next node of the answer.
s = 7 + 5 + carry # 12 digit = s % 10 # 2 carry = s // 10 # 1
Units: 2 plus 5 is 7. Write 7, carry 0.
Do not forget the last carry
Stop only when both chains are empty and no carry is left. Adding 99 and 1 gives 100: after the two digit columns there is still a carry of 1 that needs a new node.
A dummy node starts the answer, and a tail pointer follows the last node. The result is the dummy's next. Zero plus zero still produces one node holding 0, because the loop runs once on the digits.
while a or b or carry:
...
return dummy.nextAdding 5 and 5, each stored as one node. What does the result list hold?
- A0 then 1
- BA single node holding 10
- CA single node holding 0
Show the answer
0 then 1. 5 plus 5 is 10: write 0, carry 1, and the carry needs its own node.
Add two numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order (the first node is the units digit), and each node holds a single digit. Add the two numbers and return the sum as a list in the same format. The numbers have no leading zeros, except for the number 0 itself.
l1 = [2, 4, 3], l2 = [5, 6, 4] → [7, 0, 8]
1 ≤ nodes in each list ≤ 5,000 · 0 ≤ node.val ≤ 9