Add Two Numbers
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Two non-negative numbers are stored as linked lists with the digits in reverse order (ones digit first). Return their sum in the same form.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What do you do in school when the sum of a column is 10 or more?
- Hint 2Keep going while either list has digits OR there is a carry left.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Adding 342 + 465 on paper: you add the ones column, write the unit digit and carry the rest to the next column. The lists hand you the digits in exactly that order (ones first), so you just walk both lists together, add two digits plus the carry, write one digit and pass the carry on. If one number is shorter, treat its missing digits as 0.
- The obvious way
Convert both lists to integers, add, convert back: breaks for numbers with hundreds of digits in many languages.
- The key insight
Walk both lists at once. In each column: total = digit from the first (or 0) + digit from the second (or 0) + carry. Write total % 10 as a new node and carry total // 10. A dummy head makes building the answer list simple. The loop must also continue if only a carry is left.
- The algorithm
- Dummy start node; carry = 0.
- While either list has digits or a carry remains: add the two digits (0 if a list ended) and the carry.
- Write total % 10 as a new node; carry = total // 10.
- Move both lists forward. Return the dummy's next.
Watch it run
Examplefirst = 2 -> 4 -> 3 (342), second = 5 -> 6 -> 4 (465)
Ones column: 2 + 5 = 7, carry 0. Write 7.
digits so far: 7, carry 0
Where people slip
- Keep looping while a carry remains: 5 + 5 needs a third digit.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
# ListNode is provided
def add_two_numbers(first, second):
dummy = ListNode()
tail = dummy
carry = 0
while first or second or carry:
total = carry
if first:
total += first.val
first = first.next
if second:
total += second.val
second = second.next
tail.next = ListNode(total % 10) # write the digit
tail = tail.next
carry = total // 10 # pass the carry on
return dummy.nextNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.