Add Two Numbers

Problem: http://www.lintcode.com/en/problem/add-two-numbers/

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.



In [11]:

    
class Node:
    def __init__(self, value=None, next=None):
        self._value = value
        self._next = next

    @property
    def value(self):
        return self._value
    
    @property
    def next(self):
        return self._next
    
    @next.setter
    def next(self, next=None):
        self._next = next

# 123 + 456 = 579
# result: 9->7->5

a0 = Node(3)
a1 = Node(2)
a2 = Node(1)
a0.next = a1
a1.next = a2

b0 = Node(6)
b1 = Node(5)
b2 = Node(4)
b0.next = b1
b1.next = b2

def add_two_numbers(l0, l1):
    if l0 == None: return l1
    if l1 == None: return l0
    carry = 0
    dummy = Node(0)
    p = dummy
    
    while l0 and l1:
        p.next = Node((l0.value + l1.value + carry) % 10)
        carry = (l0.value + l1.value + carry) // 10
        l0 = l0.next
        l1 = l1.next
        p = p.next
    if l0:
        while l0:
            p.next = Node((l0.value + carry) % 10)
            carry = (l0.value + carry) // 10
            l0 = l0.next
            p = p.next
    if l1:
        while l1:
            p.next = Node((l1.value + carry) % 10)
            carry = (l1.value + carry) // 10
            l1 = l1.next
            p = p.next
    if carry == 1:
        p.next = Node(1)
    return dummy.next

result = Node(0)
result = add_two_numbers(a0, b0)
while (result):
    print(result.value)
    result = result.next

Add Two Number II

Problem: http://www.lintcode.com/en/problem/add-two-numbers-ii/

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in forward order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.



In [18]:

    
class Node:
    def __init__(self, value=None, next=None):
        self._value = value
        self._next = next

    @property
    def value(self):
        return self._value
    
    @property
    def next(self):
        return self._next
    
    @next.setter
    def next(self, next=None):
        self._next = next

# 876 + 456 = 1332
# result: 1->3->3->2

a0 = Node(8)
a1 = Node(7)
a2 = Node(6)
a0.next = a1
a1.next = a2

b0 = Node(4)
b1 = Node(5)
b2 = Node(6)
b0.next = b1
b1.next = b2

def add_two_numbers(l0, l1):
    if l0 is None: return l1
    if l1 is None: return l0
    
    num0 = []
    num1 = []
    
    while (l0):
        num0.append(l0.value)
        l0 = l0.next
    while (l1):
        num1.append(l1.value)
        l1 = l1.next
    
    n0 = l2n(num0)
    n1 = l2n(num1)
    n_sum = n0 + n1
    n_list = [int(x) for x in str(n_sum)]
    
    # build up the result list
    dummy = Node(0)
    p = dummy
    for n in n_list:
        p.next = Node(n)
        p = p.next
    
    return dummy.next
    
def l2n(num_list):
    if num_list is None or len(num_list) == 0: return None
    num = 0
    for i, n in enumerate(num_list):
        num += n * pow(10, len(num_list)-i-1)
    return num

result = add_two_numbers(a0, b0)
while (result):
    print(result.value)
    result = result.next



In [ ]: