CareerCup2.5.py

"""
 ============================================================================
 Question        : 2.5
                    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 Ts digit is at the head of the list. 
                    Write a function that adds the two numbers and returns the sum as a linked list.
                    EXAMPLE
                    Input:(7-> 1 -> 6) + (5 -> 9 -> 2).Thatis,617 + 295.
                    Output: 2 -> 1 -> 9.That is, 912.
                    FOLLOW UP
                    Suppose the digits are stored in forward order. Repeat the above problem. EXAMPLE
                    Input:(6 -> 1 -> 7) + (2 -> 9 -> 5).Thatis,617 + 295.
                    Output: 9 -> 1 -> 2.That is, 912.
 Solution        : add cooresponding value of two linkedlist and mark down the carry in
                   FolloUp:
                   using recusion to add two numbers and return carry
                   and save result in a list
                   reverse list and save to a linkedlist
 Time Complexity : O(n)
 Space Complexity: O(m, n)
 Gist Link       : https://gist.github.com/habina/a03e10e925ef43d95e71
 ============================================================================
"""

import random

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

    def __int__(self):
        return self.value

def print_linkedList(node):
    while node:
        if(node.value != None):
            print(node.value, end="")
        node = node.next
    print()

def initialize_linkedList(n):
    if(n <= 0):
        print("n has to lager than 0")
        return 0
    random.seed()
    head = Node(random.randint(0, 9), 0)
    n -= 1
    current = head
    while(n > 0):
        temp = Node(random.randint(0, 9), 0)
        current.next = temp
        current = temp
        n -= 1
    return head

def addTwoLinkedList(list1, list2):
    carry = 0
    newHead = Node()
    current = newHead
    while(list1 or list2):
        if(list1 and list2):
            value = list1.value + list2.value + carry
            list1 = list1.next
            list2 = list2.next
        elif(list1 and not list2):
            value = list1.value + carry
            list1 = list1.next
        elif(not list1 and list2):
            value = list2.value + carry
            list2 = list2.next

        if(value >= 10):
            value -= 10
            carry = 1
        else:
            carry = 0
        current.value = value
        current.next = Node()
        current = current.next
    if(carry == 1):
        current.value = 1
    return newHead

def followUp(list1, list2):
    if(list1.next and list2.next):
        carry = followUp(list1.next, list2.next)
    else:
        carry = 0
    value = list1.value + list2.value + carry
    if(value >= 10):
        head.append(value - 10)
        return 1
    else:
        head.append(value)
        return 0

    

a = initialize_linkedList(3)
b = initialize_linkedList(3)
c = addTwoLinkedList(a, b)
print_linkedList(a)
print_linkedList(b)
print_linkedList(c)


print("followUp")
head = []
if(followUp(a, b)):
    head.append(1)

head.reverse
result = Node()
for p in head:
    node = Node(p, result)
    result = node
print_linkedList(result)
print()