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 = Noneclass 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.nextif __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)