O(1) extra space, O(n) runtime with backtrack


  • 0
    E

    Recursion is a naturally stack.

    class Solution(object):
        add=0
        def addTwoNumbers(self, l1, l2):
            len1,len2,lt1,lt2=0,0,l1,l2
            while lt1!=None or lt2!=None:
                if lt1!=None:len1+=1;lt1=lt1.next
                if lt2!=None:len2+=1;lt2=lt2.next
            if len1>len2:
                self.backtrack(l1,l2,len1,len2)
                if self.add==1:n=ListNode(1);n.next=l1;l1=n
                return l1
            else:
                self.backtrack(l2,l1,len2,len1)
                if self.add==1:n=ListNode(1);n.next=l2;l2=n
                return l2
    
        def backtrack(self,l1,l2,len1,len2):
            if len1!=len2:
                self.backtrack(l1.next,l2,len1-1,len2)
            elif len1!=1:self.backtrack(l1.next,l2.next,len1-1,len2-1)
            self.add,l1.val=divmod(l1.val+l2.val+self.add,10) if len1==len2 else divmod(l1.val+self.add,10)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.