Problem statement

https://leetcode.com/problems/add-two-numbers

Solution

What we need to do in this problem is to perform usual schoolbook addition. Our linked lists already given in reverse order, and as in usual addition we need to start from the end. We continue to add until we still have digits to traverse. Imagine, that we need to add two numbers $986$ and $47$.

  1. add $6$ and $7$, so we have digit $3$ and carry equal to $1$.
  2. add $8$ and $4$ and $1$, so we have $3$ and carry equal to $1$.
  3. add $9$ from first number, and we do not have anything from second, so we choose $0$ from second. Also we have curry equal to $1$, finally we have digit $0$ and carry equal to $1$.
  4. We still have carry, but no digits left, so we evaluate $0 + 0 + 1 = 1$. And now we can stop, we do not have digits and we do not have carry.
  5. Final number we constructed is $1033$.

Complexity

Time complexity is $\mathcal{O}(m + n)$, where $m$ and $n$ are lengths of our linked lists, space complexity is $\mathcal{O}(\max(m, n))$ if we count answer as memory or $\mathcal{O}(1)$ if we do not.

Code

class Solution:
    def addTwoNumbers(self, l1, l2):
        carry = 0
        head = curr = ListNode(0)

        while l1 or l2 or carry:
            d1, d2 = 0, 0
            if l1: 
                d1 = l1.val
                l1 = l1.next
            if l2: 
                d2 = l2.val
                l2 = l2.next
            carry, digit = divmod(d1 + d2 + carry, 10)
            curr.next = ListNode(digit)
            curr = curr.next
              
        return head.next

If you like the solution, you can upvote it on leetcode discussion section: Problem 0002