# solution
# use one extra linked list to store the sum
# traverse two original linked list to find the sum for each digit
# pass the carry one forward
# O(max(m, n)) in time, O(max(m, n)) in space

def solution(L1, L2):
    p1 = L1
    p2 = L2
    carry = 0
    sumNode = Node() # new linked list to store the sum
    res = sumNode
    while (p1 != None) or (p2 != None) or (carry != 0):
        tmpSum = carry
        if p1 != None:
            tmpSum += p1.value
            p1 = p1.next
        if p2 != None:
            tmpSum += p2.value
            p2 = p2.next
        sumNode.value = tmpSum % 10
        carry = tmpSum / 10
        sumNode = sumNode.next
    return res

# for forward order linked list, we could reverse the linked list
# and add using the above method then reverse the result again
# O(max(m, n)) in time, O(max(m, n)) in space