# Avoid extra space by while-loop carry number

• 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

"""
: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

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
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