Intuition

The linked list is naturally in the reverse order we need to do the math. Keep a carry flag, special edge case at the final loop.

Approach

Traverse the linked list until there are no next elements in both lists. Sum both numbers, if carry is true, add 1 and set carry to false if > 9, set carry to true after the final iteration, if carry is true, add the last node with val = 1

Complexity

  • Time complexity: O(n)

  • Space complexity: O(1), just the sum

Code

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: Optional[ListNode]
        :type l2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """

        root_node = None

        n1 = l1
        n2 = l2

        carry = False

        current = None
        while n1 or n2:

            n1_val = 0 if n1 is None else n1.val
            n2_val = 0 if n2 is None else n2.val

            sum = n1_val + n2_val

            if carry:
                sum += 1
                carry = False

            if sum > 9:
                carry = True
                sum -= 10

            if root_node is None:
                root_node = ListNode(sum)
                current = root_node
            else:
                current.next = ListNode(sum)
                current = current.next

            n1 = None if not n1 else n1.next
            n2 = None if not n2 else n2.next

        if carry:
            current.next = ListNode(1)

        return root_node