Problem Description
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0] Output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: [8,9,9,9,0,0,0,1]
Constraints:
- 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.
Description taken from https://leetcode.com/problems/add-two-numbers/.
Problem Solution
#O(max(M,N)) Time, O(max(M,N)) Spaceclass Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: dummy = current = ListNode(0) carry = 0 while l1 or l2 or carry: if l1 is not None: carry += l1.val l1 = l1.next if l2 is not None: carry += l2.val l2 = l2.next current.next = ListNode(carry % 10) carry //= 10 current = current.next return dummy.nextProblem Explanation
This problem is a variation of Add Strings.
Similar to that problem, if we were to add two numbers without using an addition operator to sum them directly, we would iteratively chop off the least significant digit from the two numbers, sum them and place the value below ten into the output then carry the rest to the next iteration.
We would be doing that from right to left, but here the input numbers are reversed so that makes it easier for us because we can move through them normally and won't have to reverse the output list when we return it.
We will solve this problem by creating a third linked list using the sums of nodes from the two input lists, while also keeping track of the carry-over values.
Let's start by creating a dummy head node and a current node that we'll use as an iterator, both will be initialized from the value zero. We will also need a carry value as well for remaining digits we weren't able to fit into an output node.
dummy = current = ListNode(0) carry = 0
We will then step through both lists with a loop that will run while there are values in the first two lists that need to be added, or there is a value we still need to carry over to our output list in case we have run out of numbers to sum but still have a carry we need to place in the final iteration.
while l1 or l2 or carry:
If either one of the lists has nodes that aren't null, we will add them to the running carry value then step forward to their next node.
if l1 is not None: carry += l1.val l1 = l1.next if l2 is not None: carry += l2.val l2 = l2.next
After we have added the values of the two nodes from the input lists into the running carry value, we will create a node within our output list with the value of our carry modded by ten. This will isolate the rightmost digit of the value so that we can place it and carry over the rest.
current.next = ListNode(carry % 10)
Next, we'll chop off the digit we isolated in the previous step from the carry value.
carry //= 10
After we have placed the summed node into our output list, we will iterate to its next place.
current = current.next
Once there are no more values to add from the two input lists and we have no more values to carry over, we will return the entirety of the newly created list starting with the node after the dummy head.
return dummy.next