Avoid extra space by while-loop carry number


  • 0
    C

    No stack should be used in this problem, otherwise a very big list would blow memory.

    Instead, I process carry number by while-loop, though the worst case might be O(N^2).

    I add a break in loop and this would reduce runtime a lot (from 158ms -> 139ms).

    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
        def len(self, l):
            i = 0
            while l:
                i += 1
                l = l.next
            return i
        
        def addTwoNumbers(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """
            l_diff = self.len(l1) - self.len(l2)
            
            if l_diff < 0:
                l1, l2 = l2, l1
                l_diff = -l_diff
                
            head = tail = ListNode(0) #dummy leading zero
            
            while l1 and l_diff:
                tail.next = ListNode(l1.val)
                l1 = l1.next
                tail = tail.next
                l_diff -= 1
            
            while l1:
                if l1.val + l2.val > 9:
                    tail.val += 1
                tail.next = ListNode((l1.val + l2.val)%10)
                l1 = l1.next
                l2 = l2.next
                tail = tail.next
            
            # process carry
            carry = []
            flag = True
            while flag or carry:
                flag = False
                tail = head
                i = 0
    
                while tail:
                    if carry and carry[0] == i:
                        tail.val += 1
                        carry.pop(0)
                    if tail.val > 9:
                        carry.append(i -1)
                        tail.val -= 10
                        break # this break reduces runtime from 158ms -> 139ms
                    i += 1
                    tail = tail.next
                
            if head.val > 0:
                return head
            else:
                return head.next
    

Log in to reply
 

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