Given two numbers represented by two linked lists, write a function that returns Sum list. The sum list is linked list representation of addition of two input numbers.
Example 1:
Input:
S1 = 3, S2 = 3
ValueS1 = {2,3,4}
ValueS2 = {3,4,5}
Output: 5 7 9
Explanation: After adding the 2 numbers
the resultant number is 5 7 9.
Example 2:
Input:
S1 = 1, S2 = 2
ValueS1 = {9}
ValueS2 = {8,7}
Output: 9 6
Explanation: Add 9 and 7 we get 16.
1 is carry here and is added to 8.
So the answer is 9 6
Your Task:
The task is to complete the function addSameSize() addCarryToRemaining().
Constraints:
1 <= S1, S2 <= 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Complete search

Starter code: #User function Template for python3



'''

class Node:

    def __init__(self,data):

        self.data=data

        self.next=None

        

class llist:

    def __init__(self):

        self.head=None

        self.tail=None

        

class carry_data:

    def __init__(self):

        self.data=0

'''



#Function which adds two linked lists of same size represented by head1 

#and head2 and returns head of the resultant linked list. Carry

#is propagated while returning from the recursion

def addSameSize(h1,h2,carry):

    

    '''

    param: h1,h2: head of linked list 1 and 2

    param: carry: is instance of carry_data class, used to store carry

    return: head of resultant linked list(same size), and set the carry data, so that it could be added further

    '''

    # code here







#This function is called after the smaller list is added to the sublist of 

#bigger list of same size. Once the right sublist is added, the carry

#must be added to left side of larger list to get the final result.

def addCarryToRemaining(h1,curr,result,carry):

    

    '''

    param: h1:      head of largest linked list

    param: curr:    node till largest linked list has been added

    param: result:  resultant linked list(not head),formed from above function

    param: carry:   is instance of carry_data class, used to store carry,

    

    return: None,   set new resultant head to result linklist.

    '''

    

    # code here



Solutions:
def addSameSize(h1, h2, carry):
	if h1.next == None and h2.next == None:
		d = h1.data + h2.data
		if d >= 10:
			d -= 10
			carry.data = 1
		else:
			carry.data = 0
		return Node(d)
	c = carry_data()
	temp = addSameSize(h1.next, h2.next, c)
	d = h1.data + h2.data + c.data
	if d >= 10:
		d -= 10
		carry.data = 1
	else:
		carry.data = 0
	ans = Node(d)
	ans.next = temp
	return ans

def addCarryToRemaining(h1, curr, result, carry):
	all = []
	while h1.next != curr:
		all.append(h1)
		h1 = h1.next
	all.append(h1)
	for i in range(len(all) - 1, -1, -1):
		all[i].data += carry.data
		if all[i].data == 10:
			all[i].data = 0
		else:
			carry.data = 0
			break
	h1.next = result.head
	result.head = all[0]


ans = None

def addSameSize(h1, h2, carry):
	if h1.next == None:
		llsum = h1.data + h2.data + carry.data
		h1.data = int(llsum % 10)
		carry.data = llsum // 10
		return h1
	ll = addSameSize(h1.next, h2.next, carry)
	llsum = h1.data + h2.data + carry.data
	h1.data = int(llsum % 10)
	carry.data = llsum // 10
	return h1

def addCarryToRemaining(h1, curr, result, carry):
	st = []
	temp = h1
	while temp != curr:
		st.append(temp)
		temp = temp.next
	while len(st) > 0:
		temp = st[-1]
		st.pop()
		llsum = temp.data + carry.data
		temp.data = int(llsum % 10)
		carry.data = llsum // 10
	result.head = h1


def addSameSize(h1, h2, carry):

	def sameSize(h1, h2, carry):
		sum = h1.data + h2.data
		res = None
		if h1.next:
			res = sameSize(h1.next, h2.next, carry)
		sum += carry.data
		carry.data = sum // 10
		x = Node(sum % 10)
		x.next = res
		return x
	return sameSize(h1, h2, carry)

def addCarryToRemaining(head, curr, result_list, carry):

	def addCarry(head, curr, result_list, carry):
		if head != curr:
			addCarry(head.next, curr, result_list, carry)
			sum = head.data + carry.data
			carry.data = sum // 10
			next = result_list.head
			x = Node(sum % 10)
			x.next = next
			result_list.head = x
	addCarry(head, curr, result_list, carry)


def addSameSize(h1, h2, carry):
	if not h1:
		return
	sm = 0
	result = Node(sm)
	result.next = addSameSize(h1.next, h2.next, carry)
	sm = h1.data + h2.data + carry.data
	carry.data = sm // 10
	sm = sm % 10
	result.data = sm
	return result

def addCarryToRemaining(h1, curr, result, carry):
	if h1 != curr:
		addCarryToRemaining(h1.next, curr, result, carry)
		sm = h1.data + carry.data
		carry.data = sm // 10
		sm = sm % 10
		result.head = push(result.head, sm)
	return


def reverse(head):
	prev_node = None
	curr_node = head
	while curr_node != None:
		next_node = curr_node.next
		curr_node.next = prev_node
		prev_node = curr_node
		curr_node = next_node
	head = prev_node
	return head

class Solution:

	def addTwoLists(self, first, second):
		first = reverse(first)
		second = reverse(second)


def printLL(head):
	print('LL is - ')
	while head is not None:
		print('loop', head.data)
		head = head.next
	print('LL end ---- ')

def reverseLL(head):
	prev = None
	cur = head
	while cur:
		next = cur.next
		cur.next = prev
		prev = cur
		cur = next
	return prev

def reverseLLTillCurr(head, curr):
	prev = None
	cur = head
	while cur != curr:
		next = cur.next
		cur.next = prev
		prev = cur
		cur = next
	return prev

def addSameSize(h1, h2, carry):
	rev_h1 = reverseLL(h1)
	head = rev_h1
	rev_h2 = reverseLL(h2)
	while rev_h1:
		res = rev_h1.data + rev_h2.data + carry.data
		rev_h1.data = res % 10
		carry.data = res // 10
		rev_h1 = rev_h1.next
		rev_h2 = rev_h2.next
	head = reverseLL(head)
	return head

def addCarryToRemaining(h1, curr, result, carry):
	rev_h1 = reverseLLTillCurr(h1, curr)
	head = rev_h1
	joint = rev_h1
	while rev_h1:
		res = rev_h1.data + carry.data
		rev_h1.data = res % 10
		carry.data = res // 10
		rev_h1 = rev_h1.next
	reverseLL(head)
	joint.next = curr
	result.head = h1
	return


def addSameSize(h1, h2, carry):
	if h1 == None or h2 == None:
		return
	addSameSize(h1.next, h2.next, carry)
	cal = h1.data + h2.data + carry.data
	h1.data = cal % 10
	carry.data = cal // 10
	return h1

def addCarryToRemaining(h1, curr, result, carry):
	if h1 == curr:
		return
	addCarryToRemaining(h1.next, curr, result, carry)
	cal = h1.data + carry.data
	temp = Node(cal % 10)
	temp.next = result.head
	carry.data = cal // 10
	result.head = temp


def addSameSize(h1, h2, carry):
	if h1 is None:
		return None
	else:
		result = addSameSize(h1.next, h2.next, carry)
		total = h1.data + h2.data + carry.data
		node = Node(total % 10)
		carry.data = total // 10
		node.next = result
		return node

def addCarryToRemaining(h1, curr, result, carry):
	if h1 == curr:
		return result.head
	else:
		pointer = addCarryToRemaining(h1.next, curr, result, carry)
		total = h1.data + carry.data
		node = Node(total % 10)
		carry.data = total // 10
		node.next = pointer
		result.head = node
		return node


def addSameSize(h1, h2, carry):
	if not h1 and (not h2):
		return None
	res = addSameSize(h1.next, h2.next, carry)
	s = h1.data + h2.data + carry.data
	n = Node(s % 10)
	carry.data = s // 10
	n.next = res
	return n

def addCarryToRemaining(h1, curr, result, carry):
	if h1 == curr:
		return
	addCarryToRemaining(h1.next, curr, result, carry)
	s = h1.data + carry.data
	n = Node(s % 10)
	carry.data = s // 10
	n.next = result.head
	result.head = n


def addSameSize(h1, h2, carry):
	h1 = reverse(h1)
	h2 = reverse(h2)
	head = Node(0)
	temp = head
	while h1 and h2:
		s = h1.data + h2.data + carry.data
		head.next = Node(s % 10)
		carry.data = s // 10
		h1 = h1.next
		h2 = h2.next
		head = head.next
	temp = reverse(temp.next)
	return temp

def reverse(head):
	prev = None
	curr = head
	while curr:
		temp = curr.next
		curr.next = prev
		prev = curr
		curr = temp
	return prev

def addCarryToRemaining(h1, curr, result, carry):
	t = h1
	while t.next != curr:
		t = t.next
	if carry.data == 0:
		t.next = result.head
		result.head = h1
		return
	else:
		t.next = None
		h1 = reverse(h1)
		while h1:
			temp = h1.next
			s = h1.data + carry.data
			h1.data = s % 10
			h1.next = result.head
			result.head = h1
			carry.data = s // 10
			h1 = temp


def addSameSize(h1, h2, carry):
	num1 = 0
	num2 = 0
	while h1:
		num1 = num1 * 10 + h1.data
		h1 = h1.next
	while h2:
		num2 = num2 * 10 + h2.data
		h2 = h2.next
	res = num1 + num2
	dummy = Node(res % 10)
	res //= 10
	while res != 0:
		num = res % 10
		p = Node(num)
		p.next = dummy
		dummy = p
		res //= 10
	return dummy

def addCarryToRemaining(h1, curr, result, carry):
	count = 0
	currptr = curr
	while currptr:
		count += 1
		currptr = currptr.next
	res = result.head
	count1 = 0
	while res:
		count1 += 1
		res = res.next
	temp = h1
	num1 = 0
	while temp:
		num1 = num1 * 10 + temp.data
		if temp.next == curr:
			break
		temp = temp.next
	if count == count1:
		temp.next = result.head
		result.head = h1
		return result.head
	else:
		fn_res = num1 + 1
		result.head = result.head.next
		while fn_res != 0:
			num = fn_res % 10
			p = Node(num)
			p.next = result.head
			result.head = p
			fn_res //= 10
		return result.head


def addSameSize(h1, h2, carry):

	def reverse(head):
		prev = None
		curr = head
		next1 = None
		while curr != None:
			next1 = curr.next
			curr.next = prev
			prev = curr
			curr = next1
		return prev
	h1 = reverse(h1)
	h2 = reverse(h2)
	n = h1
	m = h2
	p = None
	headp = None
	while n != None and m != None:
		value = n.data + m.data + carry.data
		incre = value % 10
		carry.data = value // 10
		if p == None:
			p = n
			p.data = incre
			headp = p
		else:
			p.next = n
			p = p.next
			p.data = incre
		n = n.next
		m = m.next
	headp = reverse(headp)
	return headp

def addCarryToRemaining(h1, curr, result, carry):

	def reverse(head):
		prev = None
		curr = head
		next1 = None
		while curr != None:
			next1 = curr.next
			curr.next = prev
			prev = curr
			curr = next1
		return prev
	n = h1
	while n.next != curr:
		n = n.next
	n.next = None
	h1 = reverse(h1)
	p = h1
	temp = None
	while p != None:
		value = p.data + carry.data
		incre = value % 10
		carry.data = value // 10
		p.data = incre
		p = p.next
	temp = h1
	h1 = reverse(h1)
	p = h1
	h1 = p
	headp = p
	while p.next != None:
		p = p.next
	p.next = curr
	p = p.next
	result.head = headp


import sys
sys.setrecursionlimit(10000)

def addSameSize(h1, h2, carry):
	if h1 == None:
		return h1
	addSameSize(h1.next, h2.next, carry)
	ans = h1.data + h2.data + carry.data
	h1.data = ans % 10
	carry.data = ans // 10
	return h1

def addCarryToRemaining(h1, curr, result, carry):
	if h1 == curr:
		return
	addCarryToRemaining(h1.next, curr, result, carry)
	ans = h1.data + carry.data
	h1.data = ans % 10
	carry.data = ans // 10
	result.head = h1


def addSameSize(h1, h2, carry):
	if not h1:
		return
	sm = 0
	result = Node(sm)
	result.next = addSameSize(h1.next, h2.next, carry)
	sm = h1.data + h2.data + carry.data
	carry.data = sm // 10
	sm = sm % 10
	result.data = sm
	return result

def addCarryToRemaining(h1, curr, result, carry):
	if h1 != curr:
		addCarryToRemaining(h1.next, curr, result, carry)
		sm = h1.data + carry.data
		carry.data = sm // 10
		sm = sm % 10
		result.head = push(result.head, sm)
	return

class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class llist:

	def __init__(self):
		self.head = None
		self.tail = None

class carry_data:

	def __init__(self):
		self.data = 0

def append(h, t, data):
	if not h:
		h = Node(data)
		return (h, h)
	else:
		t.next = Node(data)
		return (h, t.next)

def push(head, data):
	nn = Node(data)
	nn.next = head
	return nn

def printlist(head):
	while head:
		print(head.data, end=' ')
		head = head.next
	print()

def addList(head1, head2, size1, size2, result, carry):
	if not head1:
		result.head = head2
		return
	if not head2:
		result.head = head1
		return
	if size1 == size2:
		result.head = addSameSize(head1, head2, carry)
	else:
		diff = abs(size1 - size2)
		if size1 < size2:
			(head1, head2) = (head2, head1)
		cur = head1
		for _ in range(diff):
			cur = cur.next
		result.head = addSameSize(cur, head2, carry)
		addCarryToRemaining(head1, cur, result, carry)
	if carry.data != 0:
		result.head = push(result.head, carry.data)
if __name__ == '__main__':
	t = int(input())
	for cases in range(t):
		(size1, size2) = list(map(int, input().strip().split()))
		nodes1 = list(map(int, input().strip().split()))
		nodes2 = list(map(int, input().strip().split()))
		ll1 = llist()
		ll2 = llist()
		result = llist()
		carry = carry_data()
		for e in nodes1:
			(ll1.head, ll1.tail) = append(ll1.head, ll1.tail, e)
		for e in nodes2:
			(ll2.head, ll2.tail) = append(ll2.head, ll2.tail, e)
		addList(ll1.head, ll2.head, size1, size2, result, carry)
		printlist(result.head)


def addSameSize(h1, h2, carry):
	h1 = reverseList(h1)
	h2 = reverseList(h2)
	head = h1
	while h1 != None:
		value = h1.data + h2.data + carry.data
		carry.data = value // 10
		h1.data = value % 10
		h1 = h1.next
		h2 = h2.next
	head = reverseList(head)
	return head

def addCarryToRemaining(h1, curr, result, carry):
	if carry.data != 0:
		h1 = reverseList(h1)
		curr = curr.next
		while curr != None:
			value = curr.data + carry.data
			carry.data = value // 10
			curr.data = value % 10
			curr = curr.next
		h1 = reverseList(h1)
	result.head = h1

def reverseList(head):
	curr = head
	prev = None
	while curr != None:
		temp = curr.next
		curr.next = prev
		prev = curr
		curr = temp
	return prev


def addSameSize(h1, h2, carry):
	sums = h1.data + h2.data
	ans = None
	if h1.next:
		ans = addSameSize(h1.next, h2.next, carry)
	sums += carry.data
	carry.data = sums // 10
	val = Node(sums % 10)
	val.next = ans
	return val

def addCarryToRemaining(h1, curr, result, carry):
	if h1 != curr:
		addCarryToRemaining(h1.next, curr, result, carry)
		sums = h1.data + carry.data
		carry.data = sums // 10
		next = result.head
		ans = Node(sums % 10)
		ans.next = next
		result.head = ans


def reverse(head):
	curr = head
	prev = None
	while curr:
		next1 = curr.next
		curr.next = prev
		prev = curr
		curr = next1
	return prev

def addSameSize(h1, h2, carry):
	if not h1 or not h2:
		return
	if not h1.next or not h2.next:
		if h1.data + h2.data + carry.data > 9:
			h1.data = int(str(h1.data + h2.data + carry.data)[1])
			carry.data = 1
		else:
			h1.data = h1.data + h2.data + carry.data
			carry.data = 0
		return h1
	addSameSize(h1.next, h2.next, carry)
	if h1.data + h2.data + carry.data > 9:
		h1.data = int(str(h1.data + h2.data + carry.data)[1])
		carry.data = 1
	else:
		h1.data = h1.data + h2.data + carry.data
		carry.data = 0
	return h1

def addCarryToRemaining(h1, curr, result, carry):
	if not carry.data:
		result.head = h1
		return
	prev = h1
	chck = h1.next
	while chck != curr:
		prev = chck
		chck = chck.next
	prev.next = None
	met = abc = reverse(h1)
	while abc and carry.data:
		if abc.data + carry.data > 9:
			abc.data = int(str(abc.data + carry.data)[1])
			carry.data = 1
		else:
			abc.data += carry.data
			carry.data = 0
		if not abc.next and carry.data:
			break
		abc = abc.next
	if carry.data:
		new = Node(carry.data)
		carry.data = 0
		abc.next = new
	res = reverse(met)
	met.next = chck
	result.head = res
	return


def addSameSize(h1, h2, carry):
	if h2 is None and h1 is None:
		return
	new_node = Node(0)
	if h2 is not None and h1 is not None:
		new_node.next = addSameSize(h1.next, h2.next, carry)
	elif h2 is None and h1 is not None:
		new_node.next = addSameSize(h1.next, h2, carry)
	result = (h1.data + h2.data + carry.data) % 10
	new_node.data = result
	carry.data = (h1.data + h2.data + carry.data) // 10
	return new_node

def addCarryToRemaining(h1, curr, result, carry):
	if h1 != curr:
		addCarryToRemaining(h1.next, curr, result, carry)
		sm = h1.data + carry.data
		carry.data = sm // 10
		sm = sm % 10
		result.head = push(result.head, sm)
	return


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class llist:

	def __init__(self):
		self.head = None
		self.tail = None

class carry_data:

	def __init__(self):
		self.data = 0

def addSameSize(h1, h2, carry):
	if not h1:
		return
	sm = 0
	result = Node(sm)
	result.next = addSameSize(h1.next, h2.next, carry)
	sm = h1.data + h2.data + carry.data
	carry.data = sm // 10
	sm = sm % 10
	result.data = sm
	return result

def addCarryToRemaining(h1, curr, result, carry):
	if h1 != curr:
		addCarryToRemaining(h1.next, curr, result, carry)
		sm = h1.data + carry.data
		carry.data = sm // 10
		sm = sm % 10
		result.head = push(result.head, sm)
	return


def reverse(h):
	prev = None
	while h:
		next = h.next
		h.next = prev
		prev = h
		h = next
	return prev

def addSameSize(h1, h2, carry):
	if not h1:
		return
	sm = 0
	result = Node(sm)
	result.next = addSameSize(h1.next, h2.next, carry)
	sm = h1.data + h2.data + carry.data
	carry.data = sm // 10
	sm = sm % 10
	result.data = sm
	return result

def addCarryToRemaining(h1, curr, result, carry):
	if h1 != curr:
		addCarryToRemaining(h1.next, curr, result, carry)
		sm = h1.data + carry.data
		carry.data = sm // 10
		sm = sm % 10
		result.head = push(result.head, sm)
	return


def addSameSize(h1, h2, carry):
	sm = h1.data + h2.data
	res = None
	if h1.next:
		res = addSameSize(h1.next, h2.next, carry)
	sm += carry.data
	carry.data = sm // 10
	x = Node(sm % 10)
	x.next = res
	return x

def addCarryToRemaining(head, curr, result, carry):
	if head.next != curr:
		addCarryToRemaining(head.next, curr, result, carry)
	sm = head.data + carry.data
	carry.data = sm // 10
	x = Node(sm % 10)
	x.next = result.head
	result.head = x


def addSameSize(h1, h2, carry):

	def addList1(h1, h2, c):
		if h1.next == None:
			val = h2.data + h1.data + c
			h1.data = val % 10
			return val // 10
		c = addList1(h1.next, h2.next, 0)
		val = h1.data + h2.data + c
		h1.data = val % 10
		return val // 10
	cr = addList1(h1, h2, 0)
	carry.data = cr
	return h1

def addCarryToRemaining(h1, curr, result, carry):

	def addList2(h1, curr, carry):
		if h1.next == curr:
			val = h1.data + carry.data
			h1.data = val % 10
			carry.data = val // 10
			return
		addList2(h1.next, curr, carry)
		val = h1.data + carry.data
		h1.data = val % 10
		carry.data = val // 10
		return carry.data
	addList2(h1, curr, carry)
	result.head = h1


def reverse(h):
	if h == None or h.next == None:
		return h
	curr = h
	next = h.next
	prev = None
	while next:
		curr.next = prev
		prev = curr
		curr = next
		next = curr.next
	curr.next = prev
	return curr

def addSameSize(h1, h2, carry):
	h1 = reverse(h1)
	h2 = reverse(h2)
	res = Node(0)
	p = res
	while h1 and h2:
		sum = h1.data + h2.data + carry.data
		carry.data = sum // 10
		p.next = Node(sum % 10)
		p = p.next
		h1 = h1.next
		h2 = h2.next
	res = reverse(res.next)
	return res

def addCarryToRemaining(h1, curr, result, carry):
	h1 = reverse(h1)
	curr = curr.next
	res = curr
	while curr:
		curr.data += carry.data
		carry.data = curr.data // 10
		curr.data = curr.data % 10
		curr = curr.next
	res = reverse(res)
	p = res
	while p.next:
		p = p.next
	p.next = result.head
	result.head = res


def addSameSize(h1, h2, carry):
	temp1 = h1
	temp2 = h2
	prev1 = None
	n = None
	while temp1 != None:
		n = temp1.next
		temp1.next = prev1
		prev1 = temp1
		temp1 = n
	prev2 = None
	n = None
	while temp2 != None:
		n = temp2.next
		temp2.next = prev2
		prev2 = temp2
		temp2 = n
	temp = None
	new_head = None
	c = 0
	while prev1 and prev2:
		p = (prev1.data + prev2.data + c) % 10
		c = (prev1.data + prev2.data + c) // 10
		if new_head == None:
			temp = Node(p)
			new_head = temp
		else:
			temp.next = Node(p)
			temp = temp.next
		prev1 = prev1.next
		prev2 = prev2.next
	while prev1:
		p = (prev1.data + c) % 10
		c = (prev1.data + c) // 10
		if new_head == None:
			temp = Node(p)
			new_head = temp
		else:
			temp.next = Node(p)
			temp = temp.next
		prev1 = prev1.next
	while prev2:
		p = (prev2.data + c) % 10
		c = (prev2.data + c) // 10
		if new_head == None:
			temp = Node(p)
			new_head = temp
		else:
			temp.next = Node(p)
			temp = temp.next
		prev2 = prev2.next
	if c > 0:
		carry.data = c
	temp = new_head
	prev = None
	n = None
	while temp != None:
		n = temp.next
		temp.next = prev
		prev = temp
		temp = n
	return prev

def addCarryToRemaining(h1, curr, result, carry):
	temp = h1
	while temp.next != curr:
		temp = temp.next
	temp.next = None
	temp1 = h1
	prev1 = None
	n = None
	while temp1 != None:
		n = temp1.next
		temp1.next = prev1
		prev1 = temp1
		temp1 = n
	new_head = None
	c = carry.data
	while prev1:
		p = (prev1.data + c) % 10
		c = (prev1.data + c) // 10
		if new_head == None:
			temp = Node(p)
			new_head = temp
		else:
			temp.next = Node(p)
			temp = temp.next
		prev1 = prev1.next
	temp = new_head
	prev = None
	n = None
	while temp != None:
		n = temp.next
		temp.next = prev
		prev = temp
		temp = n
	temp = prev
	while temp.next != None:
		temp = temp.next
	temp.next = result.head
	result.head = prev
	if c > 0:
		carry.data = c
	else:
		carry.data = 0


for i in range(int(input())):
	input()
	first = int(''.join(list(map(str, input().split()))))
	second = int(''.join(list(map(str, input().split()))))
	print(*str(first + second))
exit(0)

def addSameSize(h1, h2, carry):

def addCarryToRemaining(h1, curr, result, carry):


def addSameSize(h1, h2, carry):
	prev = None
	t_next = None
	t_h = h1
	while h1:
		t_next = h1.next
		h1.next = prev
		prev = h1
		h1 = t_next
	t_h = h1 = prev
	prev = None
	t_next = None
	while h2:
		t_next = h2.next
		h2.next = prev
		prev = h2
		h2 = t_next
	h2 = prev
	t_carry = 0
	while h1 and h2:
		a = h1.data
		b = h2.data
		if a + b + t_carry >= 10:
			h1.data = a + b - 10 + t_carry
			t_carry = 1
		else:
			h1.data = a + b + t_carry
			t_carry = 0
		h1 = h1.next
		h2 = h2.next
	prev = None
	t_next = None
	while t_h:
		t_next = t_h.next
		t_h.next = prev
		prev = t_h
		t_h = t_next
	carry.data = t_carry
	return prev

def addCarryToRemaining(h1, curr, result, carry):
	if h1 is None:
		return
	if h1.next == curr:
		if h1.data + carry.data >= 10:
			h1.data = h1.data + carry.data - 10
			carry.data = 1
		else:
			h1.data = h1.data + carry.data
			carry.data = 0
		result.head = h1
		return
	t_next = h1.next
	addCarryToRemaining(t_next, curr, result, carry)
	if carry.data > 0:
		if h1.data + carry.data >= 10:
			h1.data = h1.data + carry.data - 10
			carry.data = 1
		else:
			h1.data = h1.data + carry.data
			carry.data = 0
	result.head = h1