Python O(n) time, O(1) space solution, no reverse of LinkedList


  • 0
    Y
    class Solution(object):
        def addTwoNumbers(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """
            tmp1,tmp2 = l1,l2
            while tmp1 and tmp2: tmp1,tmp2 = tmp1.next,tmp2.next
            #p1 point to the longer list
            p1,p2,tmp = (l1,l2,tmp1) if tmp2==None else (l2,l1,tmp2)
            head = p1
            prevp = None
            while tmp:
                if p1.val<>9: prevp = p1
                p1,tmp = p1.next,tmp.next
            while p1:
                sumd = p1.val+p2.val
                carry,digit = sumd/10,sumd%10
                if digit==9:
                    p1.val = 9
                    p1,p2 = p1.next,p2.next
                    continue
                if carry:
                   if not prevp: 
                        head1 = ListNode(carry)
                        head1.next = head
                        head = head1
                        prevp = head
                   else: prevp.val += carry
                   while prevp.next<>p1: 
                        prevp = prevp.next
                        prevp.val = 0
                prevp = p1
                p1.val = digit
                p1,p2 = p1.next,p2.next
            return head
    

Log in to reply
 

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