[LeetCode] 2. Add Two Numbers

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

The problem equals to simulate addition operation to calculate sum of two large number.
Since number has been stored in reverse order. We only need to calculate the sum of 2 digits and carryover on each position.

Time complexity = O(Max(Len(l1), Len(l2))
Space complexity = O(Max(Len(l1), Len(l2))

#class ListNode(object):
#    def __init__(self, x):
#        self.val = x
#        self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """

        carry = 0

        dummy = ListNode(0)
        p = dummy
        
        while l1 or l2 or carry:
            num = carry

            if l1:
                num += l1.val
                l1 = l1.next

            if l2:
                num += l2.val
                l2 = l2.next

            carry = num // 10
            num = num % 10
            
            p.next = ListNode(num)
            p = p.next

        return dummy.next

A recursive solution:

# 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: ListNode, l2: ListNode) -> ListNode:
        
        def helper(p1, p2, carry):
            if p1 and p2:
                carry += p1.val + p2.val
                p1.val = carry % 10
                
                p1.next = helper(p1.next, p2.next, carry // 10)
                return p1
            
            elif p1:
                carry += p1.val
                p1.val = carry % 10
                
                p1.next = helper(p1.next, p2, carry // 10)
                return p1
            
            elif p2:
                carry += p2.val
                p2.val = carry % 10
                
                p2.next = helper(p1, p2.next, carry // 10)
                return p2
            
            elif carry:
                return ListNode(carry)
        
        return helper(l1, l2, 0)