# Time:  O(max(m, n))
# Space: O(max(m, n) + 1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        sum_head = None
        
        l1ptr, l2ptr, curr = l1, l2, None
        carry = 0
        
        # Iterate until l1 and l2 are exhausted
        while l1ptr != None or l2ptr != None:
            l1val = 0 if l1ptr is None else l1ptr.val
            l2val = 0 if l2ptr is None else l2ptr.val
            
            # Basic sum with carry on the digits
            raw_sum = l1val + l2val + carry
            sum_wo_carry = raw_sum % 10
            carry = 1 if raw_sum >= 10 else 0
            
            if sum_head is None:
                curr = ListNode(sum_wo_carry)
                sum_head = curr
            else:
                curr.next = ListNode(sum_wo_carry)
                curr = curr.next
            
            l1ptr = None if l1ptr is None else l1ptr.next
            l2ptr = None if l2ptr is None else l2ptr.next

        if carry > 0:
            curr.next = ListNode(carry)
        
        return sum_head