Description
Add two nonnegative integers represented by reversed decimal digit lists. Return the sum in the same form. Inputs are non-empty and have no unnecessary leading zeros.
Solution
def add_two_numbers(l1, l2):
dummy = tail = ListNode(0)
carry = 0
while l1 or l2 or carry:
total = carry
if l1:
total += l1.val
l1 = l1.next
if l2:
total += l2.val
l2 = l2.next
carry, digit = divmod(total, 10)
tail.next = ListNode(digit)
tail = tail.next
return dummy.nextExamples
Example 1
- Input
[[2,4,3],[5,6,4]]- Output
[7,0,8]
342 + 465 equals 807.
Example 2
- Input
[[0],[0]]- Output
[0]
Zero plus zero is zero.
Example 3
- Input
[[9,9],[1]]- Output
[0,0,1]
99 + 1 adds a most significant digit.
Approach
Walk both lists while carrying overflow. Append each total's ones digit, carry its tens digit, and stop only when both inputs and the carry are exhausted.
Time & space
O(max(m,n)) time and O(1) auxiliary space excluding output, where m and n are the list lengths.