Solutions

# Recursive. Or iterative.
# linked-lists

# Recursive - O(n) time, O(n) space
def addTwoNumbers1(l1: ListNode, l2: ListNode) -> ListNode:
    return helper(l1, l2, 0)

def helper(l1, l2, carry):
    if l1 is None and l2 is None and carry == 0:
        return None
    
    currSum = carry
    if l1 is not None:
        currSum += l1.val
    if l2 is not None:
        currSum += l2.val
        
    newNode = ListNode(currSum % 10)
    carry = currSum // 10
    if l1 is not None or l2 is not None or carry != 0:
        newNode.next = helper(l1.next if l1 is not None else None,
                                    l2.next if l2 is not None else None, 
                                    carry)
    return newNode


# Iterative - O(n) time, O(1) space
def addTwoNumbers(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode()
    cur = dummy

    carry = 0
    while l1 or l2 or carry:
        v1 = l1.val if l1 else 0
        v2 = l2.val if l2 else 0

        # new digit
        val = v1 + v2 + carry
        carry = val // 10
        val = val % 10
        cur.next = ListNode(val)

        # update ptrs
        cur = cur.next
        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None

    return dummy.next