O(1) Space, O(n) Time Python solution


  • 0
    A
    def addTwoNumbers(self, l1, l2):
        m = 0
        n = 0
        head1,head2 = l1,l2
        
        # Get length
        while l1:
            m += 1
            l1 = l1.next
        
        while l2:
            n += 1
            l2 = l2.next
            
        # To avoid checking sizes, make it such that l1 has the larger number
        if n>m:
            head1,head2 = head2,head1
            m,n = n,m
            
        res = None
        carry = 0
        
        while m:
            prev = res
            if m>n:
                new = ListNode(head1.val)
                if res:
                    res.next = new
                    res = new
                else:
                    head = new
                    res = new
                head1 = head1.next
                m -= 1
            else:
                newVal = head1.val+head2.val+carry
                new = ListNode(newVal%10)
                carry = newVal//10
                if res:
                    res.next = new
                else:
                    head = new
                res = new
                if prev:
                    prev.val += carry
                        
                elif carry:
                    newHead = ListNode(carry)
                    head = newHead
                    head.next = res
                carry = 0
                head1 = head1.next
                head2 = head2.next
                m -= 1
                n -= 1
    
        prev,curr = None,head
        
        while curr:
            if curr.val>9:
                if prev:
                    prev.val += (curr.val//10)
                    curr.val = curr.val%10
                    prev,curr = None,head
                else:
                    prev = ListNode(curr.val//10)
                    curr.val = curr.val%10
                    prev.next = curr
                    curr = prev
                    head = curr
                    prev = None
                continue
            prev = curr
            curr = curr.next
                
        return head

Log in to reply
 

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