addTwoHugeNumbers

gistfile1.txt

'''
Test cases
a = [123, 4, 5]
b = [100, 100, 100]

a = [9876, 5432, 1999]
b = [1, 8001]

a = [1]
b = [9999, 9999, 9999, 9999, 9999, 9999]

'''

'''
helper
'''
class ListNode:
    def __init__(self, x):
        self.value = x
        self.next = None

'''
helper
'''
def array_to_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    root = head
    for i in range(1, len(arr)):
        new = ListNode(arr[i])
        head.next = new
        head = new
    return root


'''
helper
'''
def linked_to_array(l):
    res = []
    while l is not None:
        res.append(l.value)
        l = l.next
    return res


'''
helper
'''
def reverse(l):
    prev = None
    head = l
    while head:
        next = head.next
        head.next = prev
        prev = head
        head = next
    return prev


def addTwoHugeNumbers(a, b):
    '''
    in order to proceed with addition from right to left
    we need to reverse linked list
    and when we finish reverse it back
    '''
    a = reverse(a)
    b = reverse(b)
    '''
    init resulting linked list
    and buffer
    '''
    head = None
    root = None
    buffer = 0
    while a or b:
        '''
        set 0 if NodeList element is already None
        '''
        a_value = 0 if not a else a.value
        b_value = 0 if not b else b.value
        sum_els = a_value + b_value
        if buffer != 0:
            sum_els = sum_els + buffer
            buffer = 0
        '''
        10000 - condition to move to another number order
        buffer - always 1 because 9 is the highest value in decimal numeral system
        '''
        if sum_els > 9999:
            sum_els = sum_els - 10000
            buffer = 1
        new = ListNode(sum_els)
        if head is None:
            head = new
            root = head
        else:
            head.next = new
            head = new
        a = None if not a else a.next
        b = None if not b else b.next
        '''
        if we have not empty buffer at the end of addition 
        then add one more NodeList to the beginning
        '''
    if buffer != 0:
        new = ListNode(buffer)
        head.next = new
    return reverse(root)


'''
we are going to do column addition like we do at school
but with only difference: addition not one by one but four by four
for example:
123,  4,  5
100,100,100
'''

a = array_to_linked_list(a)
b = array_to_linked_list(b)
result = addTwoHugeNumbers(a, b)
print(linked_to_array(result))