Python O(n) Solution without additional memory


  • 0
    Z
    class Solution(object):
        def reverse(self, l):
            if l is None or l.next is None:
                return l
            p1, p2, l.next = l, l.next, None
            while(p2 is not None):
                tmp, p2.next = p2.next, p1
                p1, p2 = p2, tmp
            return p1
                
        
        def addTwoNumbers(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """
            
            # align two lists using two pointers
            p1, p2, flag = l2, l1, 0
            while (flag<2):
                if p1.next is None:
                    p1 = l1
                    flag += 1
                else:
                    p1 = p1.next
                if p2.next is None:
                    p2 = l2
                    flag += 1
                else:
                    p2 = p2.next
    
            
            # initialize: deep copy the longer list
            pp = l1 if p1!=l1 else l2
            pp3, p3, l3 = None, None, None
            while (pp is not None):
                if l3 is None:
                    l3 = ListNode(pp.val)
                    pp3 = l3
                else:
                    pp3.next = ListNode(pp.val)
                    pp3 = pp3.next
                if pp==p1 or pp==p2:
                    p3 = pp3
                pp = pp.next
    
            # add
            pp1, pp2, pp3 = p1, p2, p3
            while (pp1 is not None):
                pp3.val = pp1.val + pp2.val
                pp1, pp2, pp3 = pp1.next, pp2.next, pp3.next
                
            pp = l3
    
            # reverse, adjust, reverse
            rl3 = self.reverse(l3)
            pp = rl3
            carry, p = 0, rl3
            while (p.next is not None):
                carry, p.val = divmod(p.val+carry, 10)
                p = p.next
            carry, p.val = divmod(p.val+carry, 10)
            p.next = ListNode(carry) if carry != 0 else None
            l3 = self.reverse(rl3)
            return l3
    

  • 0

    well done, but reversing the lists is not allowed.


  • 0
    Z

    Hi @Yuukir , I didn't reverse the input lists.


Log in to reply
 

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