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

  • 0
    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 =,
            #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 =,
            while p1:
                sumd = p1.val+p2.val
                carry,digit = sumd/10,sumd%10
                if digit==9:
                    p1.val = 9
                    p1,p2 =,
                if carry:
                   if not prevp: 
                        head1 = ListNode(carry)
               = head
                        head = head1
                        prevp = head
                   else: prevp.val += carry
                        prevp =
                        prevp.val = 0
                prevp = p1
                p1.val = digit
                p1,p2 =,
            return head

Log in to reply

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