Given two decimal numbers represented by two linked lists of size N and M respectively. The task is to return a linked list that represents the sum of these two numbers. 
For example, the number 190 will be represented by the linked list, 1->9->0->null, similarly 25 by 2->5->null. Sum of these two numbers is 190 + 25 = 215, which will be represented by 2->1->5->null. You are required to return the head of the linked list 2->1->5->null.
Example 1:
Input:
N = 2
valueN[] = {4,5}
M = 3
valueM[] = {3,4,5}
Output: 3 9 0  
Explanation: For the given two linked
list (4 5) and (3 4 5), after adding
the two linked list resultant linked
list will be (3 9 0).
Example 2:
Input:
N = 2
valueN[] = {6,3}
M = 1
valueM[] = {7}
Output: 7 0
Explanation: For the given two linked
list (6 3) and (7), after adding the
two linked list resultant linked list
will be (7 0).
Your Task:
The task is to complete the function addTwoLists() which has node reference of both the linked lists and returns the head of the sum list.   
Expected Time Complexity: O(N+M)
Expected Auxiliary Space: O(Max(N,M)) for the resultant list.
Constraints:
1 <= N, M <= 5000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



''' Node for linked list:



class Node:

    def __init__(self, data):

        self.data = data

        self.next = None



'''

class Solution:

    #Function to add two numbers represented by linked list.

    def addTwoLists(self, first, second):

        # code here

        # return head of sum list

Solutions:
class Solution:

	def addTwoLists(self, first, second):
		carry = 0
		head = Node(0)
		ans = head

		def rev(llist):
			cur = llist
			prev = None
			while cur:
				succ = cur.next
				cur.next = prev
				prev = cur
				cur = succ
			return prev
		a = rev(first)
		b = rev(second)
		carry = 0
		while a and b:
			sum = a.data + b.data + carry
			ele = sum % 10
			carry = sum // 10
			head.next = Node(ele)
			a = a.next
			b = b.next
			head = head.next
		while a:
			sum = a.data + carry
			ele = sum % 10
			carry = sum // 10
			head.next = Node(ele)
			a = a.next
			head = head.next
		while b:
			sum = b.data + carry
			ele = sum % 10
			carry = sum // 10
			head.next = Node(ele)
			b = b.next
			head = head.next
		if carry:
			head.next = Node(carry)
		an = rev(ans.next)
		return an


class Solution:

	def addTwoLists(self, first, second):
		f = ''
		s = ''
		curr = first
		while curr:
			f += str(curr.data)
			curr = curr.next
		curr = second
		while curr:
			s += str(curr.data)
			curr = curr.next
		f_s = int(f) + int(s)
		head = None
		for i in str(f_s)[::-1]:
			temp = Node(i)
			temp.next = head
			head = temp
		return head


class Solution:

	def addTwoLists(self, first, second):
		tempf = first
		fs = 0
		ss = 0
		c1 = 0
		c2 = 0
		while tempf:
			fs = fs * 10 + tempf.data
			c1 += 1
			tempf = tempf.next
		temps = second
		while temps:
			ss = ss * 10 + temps.data
			c2 += 1
			temps = temps.next
		s = fs + ss
		s = str(s)
		s = list(map(int, s))
		head = None

		def insert(self, val):
			new = Node(val)
			if self.head is None:
				self.head = new
			else:
				temp = self.head
				while temp:
					temp.data = new
					temp = temp.next
		L3 = LinkedList()
		for i in s:
			L3.insert(i)
		return L3.head


class Solution:

	def reverseList(self, head):
		a = None
		b = head
		c = None
		while b:
			c = b.next
			b.next = a
			a = b
			b = c
		return a

	def addTwoLists(self, first, second):
		first = self.reverseList(first)
		second = self.reverseList(second)
		carry = 0
		lis = []
		head1 = first
		head2 = second
		while head1 and head2:
			sum = 0
			sum = head1.data + head2.data + carry
			if sum > 9:
				carry = sum // 10
				sum = sum % 10
				lis.append(sum)
			else:
				carry = 0
				lis.append(sum)
			head1 = head1.next
			head2 = head2.next
		while head1:
			sum = head1.data + carry
			if sum > 9:
				carry = sum // 10
				sum = sum % 10
				lis.append(sum)
			else:
				carry = 0
				lis.append(sum)
			head1 = head1.next
		while head2:
			sum = head2.data + carry
			if sum > 9:
				carry = sum // 10
				sum = sum % 10
				lis.append(sum)
			else:
				carry = 0
				lis.append(sum)
			head2 = head2.next
		if carry > 0:
			lis.append(carry)
		lis.reverse()
		s = Node(lis[0])
		temp = s
		for i in range(1, len(lis)):
			temp.next = Node(lis[i])
			temp = temp.next
		return s


class Solution:

	def addTwoLists(self, first, second):
		first = self.reverseLinkedList(first)
		second = self.reverseLinkedList(second)
		dummy = Node(-1)
		curr = dummy
		carry = 0
		while first or second or carry:
			x = first.data if first else 0
			y = second.data if second else 0
			summ = x + y + carry
			carry = summ // 10
			value = summ % 10
			new_node = Node(value)
			curr.next = new_node
			curr = curr.next
			if first:
				first = first.next
			if second:
				second = second.next
		result = self.reverseLinkedList(dummy.next)
		return result

	def reverseLinkedList(self, head):
		prev = None
		curr = head
		while curr:
			next_node = curr.next
			curr.next = prev
			prev = curr
			curr = next_node
		return prev


class Solution:

	def addTwoLists(self, first, second):
		first_num = ''
		second_num = ''
		h1 = first
		while h1:
			first_num += str(h1.data)
			h1 = h1.next
		h2 = second
		while h2:
			second_num += str(h2.data)
			h2 = h2.next
		f_sum = int(first_num) + int(second_num)
		head = None
		for i in str(f_sum)[::-1]:
			new_node = Node(int(i))
			new_node.next = head
			head = new_node
		return head


class Solution:

	def reverse(self, head):
		prev = None
		curr = head
		while curr:
			next_node = curr.next
			curr.next = prev
			prev = curr
			curr = next_node
		return prev

	def addTwoLists(self, first, second):
		dummy = Node(-1)
		point = dummy
		first = self.reverse(first)
		second = self.reverse(second)
		carry = 0
		while first or second or carry:
			sum = 0
			if first:
				sum += first.data
				first = first.next
			if second:
				sum += second.data
				second = second.next
			sum += carry
			carry = sum // 10
			new_node = Node(sum % 10)
			point.next = new_node
			point = point.next
		return self.reverse(dummy.next)


class Solution:

	def addTwoLists(self, first, second):
		front = first
		prev = None
		while front is not None:
			temp = front.next
			front.next = prev
			prev = front
			front = temp
		head1 = prev
		front = second
		prev = None
		while front is not None:
			temp = front.next
			front.next = prev
			prev = front
			front = temp
		head2 = prev
		front1 = head1
		front2 = head2
		c = 0
		result = None
		while front1 is not None and front2 is not None:
			if front1.data + front2.data + c >= 10:
				node = Node((front1.data + front2.data + c) % 10)
				c = (front1.data + front2.data + c) // 10
			else:
				node = Node(front1.data + front2.data + c)
				c = 0
			if result is None:
				res_head = result = node
			else:
				result.next = node
				result = result.next
			front1 = front1.next
			front2 = front2.next
		while front1 is not None:
			if front1.data + c >= 10:
				node = Node((front1.data + c) % 10)
				c = (front1.data + c) // 10
			else:
				node = Node(front1.data + c)
				c = 0
			if result is None:
				res_head = result = node
			else:
				result.next = node
				result = result.next
			front1 = front1.next
		while front2 is not None:
			if front2.data + c >= 10:
				node = Node((front2.data + c) % 10)
				c = (front2.data + c) // 10
			else:
				node = Node(front2.data + c)
				c = 0
			if result is None:
				res_head = result = node
			else:
				result.next = node
				result = result.next
			front2 = front2.next
		if c > 0:
			result.next = Node(c)
		front = res_head
		prev = None
		while front is not None:
			temp = front.next
			front.next = prev
			prev = front
			front = temp
		return prev


class Solution:

	def addTwoLists(self, first, second):

		def reverse(node):
			itr = node
			prev = None
			while itr:
				nxt = itr.next
				itr.next = prev
				prev = itr
				itr = nxt
			return prev
		(nums1, nums2) = (0, 0)
		while first:
			nums1 = nums1 * 10 + first.data
			first = first.next
		while second:
			nums2 = nums2 * 10 + second.data
			second = second.next
		nums3 = nums1 + nums2
		tmp = Node(0)
		temp = tmp
		while nums3:
			val = nums3 % 10
			tmp.next = Node(val)
			tmp = tmp.next
			nums3 = nums3 // 10
		return reverse(temp.next)


class Solution:

	def addTwoLists(self, first, second):
		i = 0
		j = 0
		c = first
		p = None
		while c:
			n = c.next
			c.next = p
			p = c
			c = n
			i = i + 1
		first = p
		c1 = second
		p1 = None
		while c1:
			n1 = c1.next
			c1.next = p1
			p1 = c1
			c1 = n1
			j = j + 1
		second = p1
		m = max(i, j)
		t = Node(0)
		l = t
		carry = 0
		while m != 0 and t != None:
			if first and second:
				k = first.data + second.data + carry
			if first and second == None:
				k = first.data + carry
			if first == None and second != None:
				k = second.data + carry
			carry = 0
			if k <= 9:
				t.next = Node(k)
			if k > 9 and m != 1:
				k = k % 10
				t.next = Node(k)
				carry = 1
			if k > 9 and m == 1:
				k = k % 10
				t.next = Node(k)
				t = t.next
				t.next = Node(1)
				carry = 1
			t = t.next
			if first:
				first = first.next
			if second:
				second = second.next
			m = m - 1
		c2 = l.next
		p2 = None
		while c2:
			n2 = c2.next
			c2.next = p2
			p2 = c2
			c2 = n2
		return p2


class Solution:

	def addTwoLists(self, first, second):
		curr1 = first
		(num1, num2) = ('', '')
		(count1, count2) = (0, 0)
		curr2 = second
		while curr1:
			num1 += str(curr1.data)
			count1 += 1
			curr1 = curr1.next
		while curr2:
			num2 += str(curr2.data)
			count2 += 1
			curr2 = curr2.next
		ans = int(num1) + int(num2)
		new_head = Node(None)
		curr = new_head
		for digit in str(ans):
			curr.next = Node(int(digit))
			curr = curr.next
		return new_head.next


class Solution:

	def reverse(self, head):
		prev = None
		current = head
		next = None
		while current is not None:
			next = current.next
			current.next = prev
			prev = current
			current = next
		return prev

	def addTwoLists(self, first, second):
		first = self.reverse(first)
		second = self.reverse(second)
		sumList = None
		carry = 0
		while first is not None or second is not None or carry > 0:
			newVal = carry
			if first is not None:
				newVal += first.data
			if second is not None:
				newVal += second.data
			carry = newVal // 10
			newVal = newVal % 10
			newNode = Node(newVal)
			newNode.next = sumList
			sumList = newNode
			if first:
				first = first.next
			if second:
				second = second.next
		return sumList


class Solution:

	def rev(self, head):
		if head == None:
			return head
		if head.next == None:
			return head
		r = head
		head = head.next
		r.next = None
		while head != None:
			temp = r
			r = head
			head = head.next
			r.next = None
			r.next = temp
		return r

	def addTwoLists(self, first, second):
		first = self.rev(first)
		sec = self.rev(second)
		c = 0
		a = Node(-1)
		h = a
		while first != None and sec != None:
			d = c + first.data + sec.data
			h.next = Node(d % 10)
			c = d // 10
			h = h.next
			first = first.next
			sec = sec.next
		while first != None:
			d = c + first.data
			h.next = Node(d % 10)
			c = d // 10
			h = h.next
			first = first.next
		while sec != None:
			d = c + sec.data
			h.next = Node(d % 10)
			c = d // 10
			h = h.next
			sec = sec.next
		h.next = Node(c)
		ans = self.rev(a.next)
		while ans.data == 0:
			ans = ans.next
		return ans
		return


class Solution:

	def addTwoLists(self, first, second):
		a = b = ''
		while first:
			a = a + str(first.data)
			first = first.next
		while second:
			b = b + str(second.data)
			second = second.next
		c = str(int(a) + int(b))[::-1]
		p = None
		for i in c:
			temp = Node(i)
			if p is None:
				p = temp
			else:
				temp.next = p
				p = temp
		return p