from random import randint

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        carry = 0
        result = ListNode(0)
        head = result
        while l1 != None or l2 != None or carry != 0:
            single_digit_sum = 0
            if l1:
            	single_digit_sum += l1.val
            	l1 = l1.next
            if l2:
            	single_digit_sum += l2.val
            	l2 = l2.next
            single_digit_sum += carry
            current_digit_sum = single_digit_sum%10
            result.next = ListNode(current_digit_sum)
            result = result.next
            carry = single_digit_sum//10

        return head.next
def printListNode(node):
    while node != None:
    	print node.val,
	if node.next != None:
	    print '->',
	node = node.next
    print ''

def generateListNode():
    list = ListNode(randint(0,9))
    head = list
    list_len = randint(1,9)
    for i in range(list_len):
    	if i == list_len-1:
	    list.next = ListNode(randint(1,9))
	else:
	    list.next = ListNode(randint(0,9))
	list = list.next
    return head

def main():
    l1 = generateListNode()
    l2 = generateListNode()
    print 'l1: ',
    printListNode(l1)
    print 'l2: ',
    printListNode(l2)

    s = Solution()
    ans = s.addTwoNumbers(l1, l2)
    print 'ans:',
    printListNode(ans)

if __name__ == "__main__":
    main()