Add Two Numbers

　　title:　　

　　#You are given two linked lists representing two

　　#non-negative numbers. 

　　#The digits are stored.

　　#in reverse order and each of their nodes contain

　　#a single digit. 

　　#Add the two numbers and

　　#return it as a linked list.

#Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
#Output: 7 -> 0 -> 8

# methon one:array merge sum O(n+m)
# class Solution:
#     def addTwoNumbers(self, l1, l2):
#     	l3 = list()
#     	if len(l1) <= len(l2):
#     		min_len = len(l1)
#     		max_len = len(l2)
#     	else:
#     		min_len = len(l2)
#     		max_len = len(l1)
#     	l3 = [0 for i in range(max_len+1)]
#     	index = int()
#     	for i in range(min_len):
#     		if (l1[i] + l2[i] + l3[i] <= 9):
#     			l3[i] = l1[i] + l2[i] + l3[i]
#     		else:
#     			l3[i] = l1[i] + l2[i] + l3[i] - 10
#     			l3[i+1] = l3[i+1] + 1
#     		index = i + 1
#     	if index < len(l1):
#     		for i in range(index,len(l1)):
#     			if(l3[i] + l1[i] + l3[i] <= 9):
#     				l3[i] = l1[i] + l3[i]
#     			else:
#     				l3[i] = l1[i] + l3[i] - 10
#     				l3[i+1] = l3[i+1] + 1
#     	else:
#     		for i in range(index,len(l2)):
#     			if(l3[i] + l2[i] + l3[i] <= 9):
#     				l3[i] = l2[i] + l3[i]
#     			else:
#     				l3[i] = l2[i] + l3[i] - 10
#     				l3[i+1] = l3[i+1] + 1
#     	if (l3[len(l3)-1] == 0):
#     		l3.pop()
#     	return l3

# methon two:singel link merge sum O(n+m)
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    # @return a ListNode
    def addTwoNumbers(self, l1, l2):
    	#head node 
    	dummy = ListNode(-1)
    	first = l1
    	second = l2
    	prev = dummy
    	tail = dummy
    	#if beyond 10,carry = 1
    	carry = 0
    	while(first != None and second != None):
    		if (first.val + second.val + carry <= 9):
    			tail = ListNode(first.val + second.val + carry)
    			carry = 0
    			print tail.val
    		else:
    			tail = ListNode(first.val + second.val - 10 + carry)
    			carry = 1
    			print tail.val
    		#tail insert
    		prev.next = tail
    		prev = tail
    		first = first.next
    		second = second.next
    	#process remain node
    	if first != None:
    		while(first != None):
    			if (first.val + carry <= 9):
    				tail = ListNode(first.val + carry)
    				carry = 0
    				print tail.val
    			else:
    				tail = ListNode(first.val - 10 + carry)
    				carry = 1
    				print tail.val
    			prev.next = tail
    			prev = tail
    			first = first.next
    		if carry == 1:
    			tail = ListNode(1)
    			carry = 1
    			print tail.val
    			prev.next = tail
    			prev = tail
    	else:	
    		while(second != None):
    			if (second.val + carry <= 9):
    				tail = ListNode(second.val + carry)
    				carry = 0
    				print tail.val
    			else:
    				tail = ListNode(second.val - 10 + carry)
    				carry = 1
    				print tail.val
    			prev.next = tail
    			prev = tail
    			second = second.next
    		if carry == 1:
    			tail = ListNode(1)
    			carry = 1
    			print tail.val
    			prev.next = tail
    			prev = tail
    	#return head.next node
    	return dummy.next

if __name__ == '__main__':
	s = Solution()

	a = ListNode(2)
	b = ListNode(4)
	c = ListNode(3)
	l1 = a
	a.next = b
	b.next = c

	# d = ListNode(5)
	# e = ListNode(6)
	# f = ListNode(4)
	# l2 = d
	# d.next = e
	# e.next = f

	d = ListNode(9)
	e = ListNode(7)
	f = ListNode(6)
	g = ListNode(9)
	h = ListNode(9)
	i = ListNode(3)
	l2 = d
	d.next = e
	e.next = f
	f.next = g
	g.next = h
	h.next = i
	print s.addTwoNumbers(l1,l2)