Given two polynomial numbers represented by a linked list. The task is to complete the function addPolynomial() that adds these lists meaning adds the coefficients who have the same variable powers.
Note:  Given polynomials are sorted in decreasing order of power.
Example 1:
Input:
LinkedList1:  (1,x^{2) }
LinkedList2:  (1,x^{3})
Output:
1x^3 + 1x^2
Explanation: Since, x^{2} and x^{3} both have
different powers as 2 and 3. So, their
coefficient can't be added up.
Example 2:
Input:
LinkedList1:  (1,x^{3}) -> (2,x^{2})
LinkedList2:  (3,x^{3}) -> (4,x^{2})
Output:
4x^3 + 6x^2
Explanation: Since, x^{3} has two different
coefficients as 3 and 1. Adding them up
will lead to 4x^{3}. Also, x^{2} has two
coefficients as 4 and 2. So, adding them
up will give 6x^{2}.
Your Task:
The task is to complete the function addPolynomial() which should add the polynomial with same powers return the required polynomial in decreasing order of the power in the form of a linked list.
Note: Try to solve the question without using any extra space.
Expected Time Complexity: O(N+M)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N, M <= 10^{5}
1 <= x, y <= 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Mathematics

Starter code: # your task is to complete this function
'''
 class node:
    def __init__(self, coeff, pwr):
        self.coef = coeff
        self.next = None
        self.power = pwr
'''

class Solution:
    # return a linked list denoting the sum with decreasing value of power
    def addPolynomial(self, poly1, poly2):
        # Code here

Solutions:
class Solution:

	def addPolynomial(self, poly1, poly2):
		res = node(1, 1)
		temp = res
		while poly1 and poly2:
			if poly1.power > poly2.power:
				res.next = node(str(poly1.coef), str(poly1.power))
				poly1 = poly1.next
			elif poly1.power < poly2.power:
				res.next = node(str(poly2.coef), str(poly2.power))
				poly2 = poly2.next
			else:
				res.next = node(str(poly1.coef + poly2.coef), str(poly2.power))
				poly1 = poly1.next
				poly2 = poly2.next
			res = res.next
		if poly1:
			while poly1:
				res.next = node(str(poly1.coef), str(poly1.power))
				poly1 = poly1.next
				res = res.next
		if poly2:
			while poly2:
				res.next = node(str(poly2.coef), str(poly2.power))
				poly2 = poly2.next
				res = res.next
		return temp.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		ll = Linked_List()
		while poly1 and poly2:
			if poly1.power < poly2.power:
				ll.insert(poly2.coef, poly2.power)
				poly2 = poly2.next
			elif poly1.power > poly2.power:
				ll.insert(poly1.coef, poly1.power)
				poly1 = poly1.next
			else:
				ll.insert(poly1.coef + poly2.coef, poly1.power)
				poly1 = poly1.next
				poly2 = poly2.next
		while poly1:
			ll.insert(poly1.coef, poly1.power)
			poly1 = poly1.next
		while poly2:
			ll.insert(poly2.coef, poly2.power)
			poly2 = poly2.next
		return ll.head


class Solution:

	def addPolynomial(self, poly1, poly2):
		ans = None
		while poly1 and poly2:
			if poly1.power > poly2.power:
				data = poly1
				poly1 = poly1.next
				data.next = None
				if ans == None:
					ans = data
					temp = ans
				else:
					temp.next = data
					temp = temp.next
			elif poly1.power < poly2.power:
				data = poly2
				poly2 = poly2.next
				data.next = None
				if ans == None:
					ans = data
					temp = ans
				else:
					temp.next = data
					temp = temp.next
			elif poly1.power == poly2.power:
				data1 = poly1
				data2 = poly2
				poly1 = poly1.next
				poly2 = poly2.next
				data1.next = None
				data2.next = None
				data1.coef = data1.coef + data2.coef
				if ans == None:
					ans = data1
					temp = ans
				else:
					temp.next = data1
					temp = temp.next
		while poly1:
			data = poly1
			poly1 = poly1.next
			data.next = None
			if ans == None:
				ans = data
				temp = ans
			else:
				temp.next = data
				temp = temp.next
		while poly2:
			data = poly2
			poly2 = poly2.next
			data.next = None
			if ans == None:
				ans = data
				temp = ans
			else:
				temp.next = data
				temp = temp.next
		return ans


class Solution:

	def addPolynomial(self, poly1, poly2):
		t1 = poly1
		t2 = poly2
		dummy = node(0, 0)
		temp = dummy
		while t1 and t2:
			if t1.power > t2.power:
				temp.next = t1
				t1 = t1.next
			elif t1.power == t2.power:
				t1.coef += t2.coef
				temp.next = t1
				t1 = t1.next
				t2 = t2.next
			else:
				temp.next = t2
				t2 = t2.next
			temp = temp.next
		if t1:
			temp.next = t1
		if t2:
			temp.next = t2
		return dummy.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		p1 = poly1
		p2 = poly2
		res = Linked_List()
		while p1 != None and p2 != None:
			if p1.power == p2.power:
				res.insert(p1.coef + p2.coef, p1.power)
				p1 = p1.next
				p2 = p2.next
			elif p1.power > p2.power:
				res.insert(p1.coef, p1.power)
				p1 = p1.next
			else:
				res.insert(p2.coef, p2.power)
				p2 = p2.next
		while p1 != None:
			res.insert(p1.coef, p1.power)
			p1 = p1.next
		while p2 != None:
			res.insert(p2.coef, p2.power)
			p2 = p2.next
		return res.head


class Solution:

	def addPolynomial(self, poly1, poly2):
		p1 = poly1
		p2 = poly2
		head = None
		temp = None
		while p1 != None and p2 != None:
			if p1.power == p2.power:
				new = node(p1.coef + p2.coef, p1.power)
				if temp == None:
					temp = new
					head = new
				else:
					temp.next = new
					temp = new
				p1 = p1.next
				p2 = p2.next
			elif p1.power > p2.power:
				new = node(p1.coef, p1.power)
				if temp == None:
					temp = new
					head = new
				else:
					temp.next = new
					temp = new
				p1 = p1.next
			else:
				new = node(p2.coef, p2.power)
				if temp == None:
					temp = new
					head = new
				else:
					temp.next = new
					temp = new
				p2 = p2.next
		while p1 != None:
			new = node(p1.coef, p1.power)
			if temp == None:
				temp = new
				head = new
			else:
				temp.next = new
				temp = new
			p1 = p1.next
		while p2 != None:
			new = node(p2.coef, p2.power)
			if temp == None:
				temp = new
				head = new
			else:
				temp.next = new
				temp = new
			p2 = p2.next
		return head


class Solution:

	def addPolynomial(self, poly1, poly2):
		x = poly1
		y = poly2
		res = Linked_List()
		while x != None and y != None:
			if x.power == y.power:
				res.insert(x.coef + y.coef, x.power)
				x = x.next
				y = y.next
			elif x.power > y.power:
				res.insert(x.coef, x.power)
				x = x.next
			else:
				res.insert(y.coef, y.power)
				y = y.next
		while x != None:
			res.insert(x.coef, x.power)
			x = x.next
		while y != None:
			res.insert(y.coef, y.power)
			y = y.next
		return res.head


def reverse(head):
	pre = None
	while head:
		nxt = head.next
		head.next = pre
		pre = head
		head = nxt
	return pre

class Solution:

	def addPolynomial(self, poly1, poly2):
		head1 = reverse(poly1)
		head2 = reverse(poly2)
		temp = None
		tmp = None
		while head1 and head2:
			if head1.power == head2.power:
				if not temp:
					head1.coef = head1.coef + head2.coef
					temp = head1
					head1 = head1.next
					head2 = head2.next
					tmp = temp
				else:
					head1.coef = head1.coef + head2.coef
					temp.next = head1
					temp = temp.next
					head1 = head1.next
					head2 = head2.next
			elif head1.power < head2.power:
				if not temp:
					temp = head1
					tmp = temp
				else:
					temp.next = head1
					temp = temp.next
				head1 = head1.next
			else:
				if not temp:
					temp = head2
					tmp = temp
				else:
					temp.next = head2
					temp = temp.next
				head2 = head2.next
		while head1:
			temp.next = head1
			temp = temp.next
			head1 = head1.next
		while head2:
			temp.next = head2
			temp = temp.next
			head2 = head2.next
		temp.next = None
		tmp = reverse(tmp)
		return tmp


class Solution:

	def addPolynomial(self, poly1, poly2):
		ans = node(-1, -1)
		prev = ans
		while poly1 or poly2:
			if poly1 == None:
				prev.next = poly2
				break
			elif poly2 == None:
				prev.next = poly1
				break
			elif poly1.power > poly2.power:
				prev.next = poly1
				poly1 = poly1.next
			elif poly1.power < poly2.power:
				prev.next = poly2
				poly2 = poly2.next
			else:
				prev.next = node(poly1.coef + poly2.coef, poly1.power)
				poly1 = poly1.next
				poly2 = poly2.next
			prev = prev.next
		return ans.next


class Solution:

	def addPolynomial(self, p1, p2):
		a = p1
		b = p2
		newHead = node(0, 0)
		c = newHead
		while a != None or b != None:
			if a == None:
				c.next = b
				break
			elif b == None:
				c.next = a
				break
			elif a.power == b.power:
				c.next = node(a.coef + b.coef, a.power)
				a = a.next
				b = b.next
			elif a.power > b.power:
				c.next = node(a.coef, a.power)
				a = a.next
			elif a.power < b.power:
				c.next = node(b.coef, b.power)
				b = b.next
			c = c.next
		return newHead.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		ptr1 = poly1
		ptr2 = poly2
		dum = node(-1, -1)
		dp = dum
		while ptr1 and ptr2:
			if ptr1.power > ptr2.power:
				dp.next = ptr1
				ptr1 = ptr1.next
				dp = dp.next
			elif ptr1.power < ptr2.power:
				dp.next = ptr2
				ptr2 = ptr2.next
				dp = dp.next
			else:
				ptr1.coef = ptr1.coef + ptr2.coef
				dp.next = ptr1
				ptr1 = ptr1.next
				ptr2 = ptr2.next
				dp = dp.next
		while ptr1:
			dp.next = ptr1
			ptr1 = ptr1.next
			dp = dp.next
		while ptr2:
			dp.next = ptr2
			ptr2 = ptr2.next
			dp = dp.next
		return dum.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		ll1 = poly1
		ll2 = poly2
		head = None
		tail = None
		while ll1 != None and ll2 != None:
			if ll1.power == ll2.power:
				newnode = node(ll1.coef + ll2.coef, ll1.power)
				if head == None:
					head = newnode
					tail = newnode
				else:
					tail.next = newnode
					tail = newnode
				ll1 = ll1.next
				ll2 = ll2.next
			elif ll1.power > ll2.power:
				newnode = node(ll1.coef, ll1.power)
				if head == None:
					head = newnode
					tail = newnode
				else:
					tail.next = newnode
					tail = newnode
				ll1 = ll1.next
			else:
				newnode = node(ll2.coef, ll2.power)
				if head == None:
					head = newnode
					tail = newnode
				else:
					tail.next = newnode
					tail = newnode
				ll2 = ll2.next
		while ll1 != None:
			newnode = node(ll1.coef, ll1.power)
			if head == None:
				head = newnode
				tail = newnode
			else:
				tail.next = newnode
				tail = newnode
			ll1 = ll1.next
		while ll2 != None:
			newnode = node(ll2.coef, ll2.power)
			if head == None:
				head = newnode
				tail = newnode
			else:
				tail.next = newnode
				tail = newnode
			ll2 = ll2.next
		return head


class Solution:

	def addPolynomial(self, poly1, poly2):
		start = node(0, 0)
		head = start
		while poly1 and poly2:
			if poly1.power > poly2.power:
				head.next = node(poly1.coef, poly1.power)
				head = head.next
				poly1 = poly1.next
			elif poly1.power < poly2.power:
				head.next = node(poly2.coef, poly2.power)
				head = head.next
				poly2 = poly2.next
			else:
				head.next = node(poly1.coef + poly2.coef, poly1.power)
				head = head.next
				poly1 = poly1.next
				poly2 = poly2.next
		while poly1:
			head.next = node(poly1.coef, poly1.power)
			head = head.next
			poly1 = poly1.next
		while poly2:
			head.next = node(poly2.coef, poly2.power)
			head = head.next
			poly2 = poly2.next
		return start.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		mp = {}
		cur = poly1
		while cur:
			try:
				mp[cur.power] += cur.coef
			except KeyError:
				mp[cur.power] = cur.coef
			cur = cur.next
		cur = poly2
		while cur:
			try:
				mp[cur.power] += cur.coef
			except KeyError:
				mp[cur.power] = cur.coef
			cur = cur.next
		res = Linked_List()
		lst = list(mp.items())
		for i in lst[::-1]:
			res.insert(i[1], i[0])
		return res.head


class Solution:

	def addPolynomial(self, poly1, poly2):
		d = {}
		while poly1 != None:
			if d.get(poly1.power) == None:
				d[poly1.power] = 0
			d[poly1.power] += poly1.coef
			poly1 = poly1.next
		while poly2 != None:
			if d.get(poly2.power) == None:
				d[poly2.power] = 0
			d[poly2.power] += poly2.coef
			poly2 = poly2.next
		arr = [[x, d[x]] for x in sorted(d.keys(), reverse=True)]
		ans = node(arr[0][1], arr[0][0])
		cans = ans
		for x in arr[1:]:
			cans.next = node(x[1], x[0])
			cans = cans.next
		return ans


class node:

	def __init__(self, coeff, pwr):
		self.coef = coeff
		self.next = None
		self.power = pwr

class Solution:

	def addPolynomial(self, poly1, poly2):
		res = node(1, 1)
		temp = res
		while poly1 and poly2:
			if poly1.power > poly2.power:
				res.next = node(str(poly1.coef), str(poly1.power))
				poly1 = poly1.next
			elif poly1.power < poly2.power:
				res.next = node(str(poly2.coef), str(poly2.power))
				poly2 = poly2.next
			else:
				res.next = node(str(poly1.coef + poly2.coef), str(poly2.power))
				poly1 = poly1.next
				poly2 = poly2.next
			res = res.next
		if poly1:
			while poly1:
				res.next = node(str(poly1.coef), str(poly1.power))
				poly1 = poly1.next
				res = res.next
		if poly2:
			while poly2:
				res.next = node(str(poly2.coef), str(poly2.power))
				poly2 = poly2.next
				res = res.next
		return temp.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		temp = poly1
		prev1 = None
		while temp:
			nxt = temp.next
			temp.next = prev1
			prev1 = temp
			temp = nxt
		temp = poly2
		prev2 = None
		while temp:
			nxt = temp.next
			temp.next = prev2
			prev2 = temp
			temp = nxt
		ans = nd = node(-1, 3)
		carry = 0
		while prev1 and prev2:
			if prev1.power == prev2.power:
				val = prev1.coef + prev2.coef
				nd.next = node(val, prev1.power)
				nd = nd.next
				prev1 = prev1.next
				prev2 = prev2.next
			elif prev1.power < prev2.power:
				val = prev1.coef
				nd.next = node(val, prev1.power)
				nd = nd.next
				prev1 = prev1.next
			else:
				val = prev2.coef
				nd.next = node(val, prev2.power)
				nd = nd.next
				prev2 = prev2.next
		while prev1:
			val = prev1.coef
			nd.next = node(val, prev1.power)
			nd = nd.next
			prev1 = prev1.next
		while prev2:
			val = prev2.coef
			nd.next = node(val, prev2.power)
			nd = nd.next
			prev2 = prev2.next
		prev = None
		temp = ans.next
		while temp:
			nxt = temp.next
			temp.next = prev
			prev = temp
			temp = nxt
		return prev


class Solution:

	def addPolynomial(self, poly1, poly2):
		ans = res = node(0, 0)
		if poly1.power < poly2.power:
			(poly1, poly2) = (poly2, poly1)
		while poly1 and poly2 and (poly1.power > poly2.power):
			res.next = poly1
			res = res.next
			poly1 = poly1.next
		while poly1 and poly2:
			res.next = node(poly1.coef + poly2.coef, poly1.power)
			res = res.next
			poly1 = poly1.next
			poly2 = poly2.next
		while poly1:
			res.next = poly1
			res = res.next
			poly1 = poly1.next
		while poly2:
			res.next = poly2
			res = res.next
			poly2 = poly2.next
		return ans.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		p1 = poly1
		p2 = poly2
		newPoly = node(0, 0)
		p3 = newPoly
		while p1 or p2:
			if p1 and p2:
				if p1.power < p2.power:
					p3.next = node(p2.coef, p2.power)
					p2 = p2.next
				elif p1.power > p2.power:
					p3.next = node(p1.coef, p1.power)
					p1 = p1.next
				elif p1.power == p2.power:
					p3.next = node(p1.coef + p2.coef, p1.power)
					p1 = p1.next
					p2 = p2.next
			elif p2 and (not p1):
				p3.next = node(p2.coef, p2.power)
				p2 = p2.next
			elif p1 and (not p2):
				p3.next = node(p1.coef, p1.power)
				p1 = p1.next
			p3 = p3.next
		return newPoly.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		dummy = node('x', 0)
		pre = dummy
		while poly1 is not None and poly2 is not None:
			if poly1.power == poly2.power:
				pre.next = node(poly1.coef + poly2.coef, poly1.power)
				poly1 = poly1.next
				poly2 = poly2.next
				pre = pre.next
			elif poly1.power > poly2.power:
				pre.next = node(poly1.coef, poly1.power)
				pre = pre.next
				poly1 = poly1.next
			else:
				pre.next = node(poly2.coef, poly2.power)
				pre = pre.next
				poly2 = poly2.next
		while poly1 is not None:
			pre.next = node(poly1.coef, poly1.power)
			poly1 = poly1.next
			pre = pre.next
		while poly2 is not None:
			pre.next = node(poly2.coef, poly2.power)
			poly2 = poly2.next
			pre = pre.next
		return dummy.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		if not poly1:
			return poly2
		if not poly2:
			return poly1
		res = None
		resa = None
		p1 = poly1
		p2 = poly2
		while p1 and p2:
			if p1.power > p2.power:
				if not res:
					res = node(p1.coef, p1.power)
					resa = res
				else:
					res.next = node(p1.coef, p1.power)
					res = res.next
				p1 = p1.next
				continue
			elif p2.power > p1.power:
				if not res:
					res = node(p2.coef, p2.power)
					resa = res
				else:
					res.next = node(p2.coef, p2.power)
					res = res.next
				p2 = p2.next
				continue
			else:
				c = p1.coef + p2.coef
				x = node(c, p1.power)
				if not res:
					res = x
					resa = res
				else:
					res.next = x
					res = res.next
				p1 = p1.next
				p2 = p2.next
		if p1:
			res.next = p1
		if p2:
			res.next = p2
		return resa


class Solution:

	def addPolynomial(self, poly1, poly2):
		dummy = node(-1, -1)
		temp = dummy
		cur1 = poly1
		cur2 = poly2
		while cur1 and cur2:
			if cur1.power < cur2.power:
				temp.next = node(cur2.coef, cur2.power)
				temp = temp.next
				cur2 = cur2.next
			elif cur1.power > cur2.power:
				temp.next = node(cur1.coef, cur1.power)
				temp = temp.next
				cur1 = cur1.next
			else:
				coeff_sum = cur1.coef + cur2.coef
				temp.next = node(coeff_sum, cur1.power)
				temp = temp.next
				cur1 = cur1.next
				cur2 = cur2.next
		while cur1:
			temp.next = node(cur1.coef, cur1.power)
			temp = temp.next
			cur1 = cur1.next
		while cur2:
			temp.next = node(cur2.coef, cur2.power)
			temp = temp.next
			cur2 = cur2.next
		return dummy.next


class Solution:

	def addPolynomial(self, head1, head2):
		cur1 = head1
		cur2 = head2
		prev1 = prev2 = None
		while cur1 and cur2:
			if cur1.power == cur2.power:
				cur1.coef += cur2.coef
				prev1 = cur1
				prev2 = cur2
				cur1 = cur1.next
				cur2 = cur2.next
			elif cur1.power > cur2.power:
				prev1 = cur1
				cur1 = cur1.next
			elif cur1.power < cur2.power:
				temp = cur2
				pow = cur1.power
				while temp.power > pow:
					fuck = temp
					temp = temp.next
					if temp == None:
						break
				if prev1 != None:
					prev1.next = cur2
					fuck.next = cur1
					cur2 = temp
				else:
					temp2 = fuck.next
					fuck.next = cur1
					head1 = cur2
					cur2 = temp2
		if cur2 != None:
			prev1.next = curr2
		return head1


class Solution:

	def addPolynomial(self, poly1, poly2):
		primenode = runnode = node(None, None)
		while poly1 != None and poly2 != None:
			if poly1.power > poly2.power:
				runnode.next = poly1
				runnode = runnode.next
				poly1 = poly1.next
			elif poly1.power < poly2.power:
				runnode.next = poly2
				runnode = runnode.next
				poly2 = poly2.next
			else:
				poly1.coef = poly1.coef + poly2.coef
				runnode.next = poly1
				runnode = runnode.next
				poly1 = poly1.next
				poly2 = poly2.next
		runnode.next = poly2 if poly1 == None else poly1
		return primenode.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		primenode = runnode = node(None, None)
		while poly1 != None or poly2 != None:
			if poly1 == None or poly2 == None:
				poly = poly2 if poly1 == None else poly1
				runnode.next = poly
				break
			if poly1.power > poly2.power:
				runnode.next = poly1
				runnode = runnode.next
				poly1 = poly1.next
			elif poly1.power < poly2.power:
				runnode.next = poly2
				runnode = runnode.next
				poly2 = poly2.next
			else:
				poly1.coef = poly1.coef + poly2.coef
				runnode.next = poly1
				runnode = runnode.next
				poly1 = poly1.next
				poly2 = poly2.next
		return primenode.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		result = node(0, 0)
		temp = result
		while poly1 != None and poly2 != None:
			if poly1.power == poly2.power:
				n = node(poly1.coef + poly2.coef, poly1.power)
				poly1 = poly1.next
				poly2 = poly2.next
			elif poly1.power > poly2.power:
				n = node(poly1.coef, poly1.power)
				poly1 = poly1.next
			else:
				n = node(poly2.coef, poly2.power)
				poly2 = poly2.next
			temp.next = n
			temp = temp.next
		if poly1 != None:
			temp.next = poly1
		if poly2 != None:
			temp.next = poly2
		return result.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		nn = node(0, 0)
		n = nn
		while poly1 != None and poly2 != None:
			if poly1.power == poly2.power:
				sum = poly1.coef + poly2.coef
				newNode = node(sum, poly1.power)
				poly1 = poly1.next
				poly2 = poly2.next
			elif poly1.power > poly2.power:
				newNode = node(poly1.coef, poly1.power)
				poly1 = poly1.next
			else:
				newNode = node(poly2.coef, poly2.power)
				poly2 = poly2.next
			n.next = newNode
			n = n.next
		if poly1 != None:
			newNode = node(poly1.coef, poly1.power)
			poly1 = poly1.next
			n.next = newNode
			n = n.next
		if poly2 != None:
			newNode = node(poly1.coef, poly2.power)
			poly2 = poly2.next
			n.next = newNode
			n = n.next
		return nn.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		head = node(-1, -1)
		temp = head
		while poly1 != None and poly2 != None:
			if poly1.power > poly2.power:
				if temp.power == poly1.power:
					temp.coef = temp.coef + poly1.power
					poly1 = poly1.next
				else:
					temp.next = node(poly1.coef, poly1.power)
					poly1 = poly1.next
					temp = temp.next
			elif poly1.power < poly2.power:
				if poly2.power == temp.power:
					temp.coef = temp.coef + poly2.power
					poly2 = poly2.next
				else:
					temp.next = node(poly2.coef, poly2.power)
					poly2 = poly2.next
					temp = temp.next
			elif temp.power == poly1.power:
				temp.coef = temp.coef + poly1.coef + poly2.coef
				poly1 = poly1.next
				poly2 = poly2.next
			else:
				temp.next = node(poly1.coef + poly2.coef, poly1.power)
				poly1 = poly1.next
				poly2 = poly2.next
				temp = temp.next
		while poly1 != None:
			if temp.power == poly1.power:
				temp.coef = temp.coef + poly1.power
				poly1 = poly1.next
			else:
				temp.next = node(poly1.coef, poly1.power)
				poly1 = poly1.next
				temp = temp.next
		while poly2 != None:
			if poly2.power == temp.power:
				temp.coef = temp.coef + poly2.power
				poly2 = poly2.next
			else:
				temp.next = node(poly2.coef, poly2.power)
				poly2 = poly2.next
				temp = temp.next
		return head.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		node1 = node(0, 0)
		c = node1
		while 1:
			if poly1 == None:
				c.next = poly2
				break
			elif poly2 == None:
				c.next = poly1
				break
			elif poly2.power > poly1.power:
				c.next = poly2
				poly2 = poly2.next
			elif poly2.power < poly1.power:
				c.next = poly1
				poly1 = poly1.next
			elif poly1.power == poly2.power:
				Newnode = node(poly1.coef + poly2.coef, poly1.power)
				c.next = Newnode
				poly1 = poly1.next
				poly2 = poly2.next
			c = c.next
		return node1.next


class Solution:

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

	def addPolynomial(self, poly1, poly2):
		dict1 = {}
		m = poly2
		n = poly1
		while m:
			dict1[m.power] = m.coef
			m = m.next
		while n:
			if n.power in dict1:
				dict1[n.power] += n.coef
			else:
				dict1[n.power] = n.coef
			n = n.next
		m = poly2
		a = True
		for i in sorted(dict1.keys()):
			if m.next:
				m.coef = dict1[i]
				m.power = i
				m = m.next
			elif a:
				m.coef = dict1[i]
				m.power = i
				a = False
			else:
				m.next = node(dict1[i], i)
				m = m.next
		return self.reverse(poly2)


class Solution:

	def addPolynomial(self, poly1, poly2):
		a = poly1
		b = poly2
		newHead = node(0, 0)
		c = newHead
		while a != None or b != None:
			if a == None:
				c.next = b
				break
			elif b == None:
				c.next = a
				break
			elif a.power == b.power:
				c.next = node(a.coef + b.coef, a.power)
				a = a.next
				b = b.next
			elif a.power > b.power:
				c.next = node(a.coef, a.power)
				a = a.next
			elif a.power < b.power:
				c.next = node(b.coef, b.power)
				b = b.next
			c = c.next
		return newHead.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		if poly1.power < poly2.power:
			(poly1, poly2) = (poly2, poly1)
		cur1 = poly1
		ans = poly1
		cur2 = poly2
		tail = None
		while cur1:
			if cur1.power > cur2.power:
				if cur1.next is None:
					tail = cur1
				cur1 = cur1.next
			elif cur1.power == cur2.power:
				cur1.coef += cur2.coef
				if cur1.next is None:
					tail = cur1
				cur1 = cur1.next
				cur2 = cur2.next
			else:
				n = node(cur1.coef, cur1.power)
				n.next = cur1.next
				cur1.next = n
				cur1.coef = cur2.coef
				cur1.power = cur2.power
				cur2 = cur2.next
				cur1 = cur1.next
		if cur2:
			tail.next = cur2
		return ans


class Solution:

	def addPolynomial(self, poly1, poly2):
		eqn1 = poly1
		eqn2 = poly2
		if poly1.power > poly2.power:
			eqn3 = node(poly1.coef, poly1.power)
			poly3 = eqn3
			eqn1 = eqn1.next
		elif poly1.power < poly2.power:
			eqn3 = node(poly2.coef, poly2.power)
			poly3 = eqn3
			eqn2 = eqn2.next
		else:
			eqn3 = node(poly1.coef + poly2.coef, poly1.power)
			poly3 = eqn3
			eqn1 = eqn1.next
			eqn2 = eqn2.next
		while eqn1 is not None and eqn2 is not None:
			if eqn1.power > eqn2.power:
				eqn3.next = node(eqn1.coef, eqn1.power)
				eqn3 = eqn3.next
				eqn1 = eqn1.next
			elif eqn1.power < eqn2.power:
				eqn3.next = node(eqn2.coef, eqn2.power)
				eqn3 = eqn3.next
				eqn2 = eqn2.next
			elif eqn1.power == eqn2.power:
				eqn3.next = node(eqn1.coef + eqn2.coef, eqn1.power)
				eqn3 = eqn3.next
				eqn1 = eqn1.next
				eqn2 = eqn2.next
		while eqn1 is not None:
			eqn3.next = node(eqn1.coef, eqn1.power)
			eqn3 = eqn3.next
			eqn1 = eqn1.next
		while eqn2 is not None:
			eqn3.next = node(eqn2.coef, eqn2.power)
			eqn3 = eqn3.next
			eqn2 = eqn2.next
		return poly3


class Solution:

	def addPolynomial(self, poly1, poly2):
		a = poly1
		b = poly2
		dummy = node(0, 0)
		tail = dummy
		tail.next = None
		while 1:
			if poly1 is None:
				tail.next = poly2
				break
			if poly2 is None:
				tail.next = poly1
				break
			if poly1.power == poly2.power:
				tail.next = node(poly1.coef + poly2.coef, poly1.power)
				tail = tail.next
				poly1 = poly1.next
				poly2 = poly2.next
			elif poly1.power > poly2.power:
				tail.next = poly1
				poly1 = poly1.next
				tail = tail.next
			else:
				tail.next = poly2
				poly2 = poly2.next
				tail = tail.next
		return dummy.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		try:
			res = head = None
			while poly1 and poly2:
				if poly1.power == poly2.power:
					if not res:
						head = res = poly1
					else:
						res.next = poly1
						res = res.next
					poly1.coef += poly2.coef
					poly1 = poly1.next
					poly2 = poly2.next
				elif poly1.power > poly2.power:
					if not head:
						head = res = poly1
					else:
						res.next = poly1
						res = res.next
					poly1 = poly1.next
				else:
					if not head:
						head = res = poly2
					else:
						res.next = poly2
						res = res.next
					poly2 = poly2.next
			if res:
				if poly1:
					res.next = poly1
				else:
					res.next = poly2
		except Exception as e:
			print(e)
		return head


class Solution:

	def addPolynomial(self, poly1, poly2):
		a = poly1
		b = poly2
		newnode = node(0, 0)
		c = newnode
		while a or b:
			if not a:
				c.next = b
				break
			if not b:
				c.next = a
				break
			if a.power == b.power:
				c.next = node(a.coef + b.coef, a.power)
				a = a.next
				b = b.next
			elif a.power > b.power:
				c.next = node(a.coef, a.power)
				a = a.next
			elif b.power > a.power:
				c.next = node(b.coef, b.power)
				b = b.next
			c = c.next
		return newnode.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		p = poly1
		q = poly2
		s = ''
		t = None
		head = None
		while p and q:
			if p.power == q.power:
				p.coef += q.coef
				if t == None:
					t = p
					head = p
				else:
					t.next = p
					t = t.next
				p = p.next
				q = q.next
			elif p.power > q.power:
				if t == None:
					t = p
					head = p
				else:
					t.next = p
					t = t.next
				p = p.next
			else:
				if t == None:
					t = q
					head = q
				else:
					t.next = q
					t = t.next
				q = q.next
		if p:
			t.next = p
		if q:
			t.next = q
		return head


class Solution:

	def addPolynomial(self, p1, p2):
		head = node(0, 0)
		dummy = head
		while p1 and p2:
			if p1.power == p2.power:
				p1.coef += p2.coef
				dummy.next = p1
				p1 = p1.next
				p2 = p2.next
				dummy = dummy.next
			elif p1.power > p2.power:
				dummy.next = p1
				p1 = p1.next
				dummy = dummy.next
			elif p2.power > p1.power:
				dummy.next = p2
				p2 = p2.next
				dummy = dummy.next
		if p1:
			dummy.next = p1
		if p2:
			dummy.next = p2
		return head.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		ptr1 = poly1
		ptr2 = poly2
		sum = Linked_List()
		while ptr1 and ptr2:
			if ptr1.power == ptr2.power:
				new_coef = ptr1.coef + ptr2.coef
				sum.insert(new_coef, ptr1.power)
				ptr1 = ptr1.next
				ptr2 = ptr2.next
			elif ptr1.power > ptr2.power:
				sum.insert(ptr1.coef, ptr1.power)
				ptr1 = ptr1.next
			elif ptr2.power > ptr1.power:
				sum.insert(ptr2.coef, ptr2.power)
				ptr2 = ptr2.next
		while ptr1:
			sum.insert(ptr1.coef, ptr1.power)
			ptr1 = ptr1.next
		while ptr2:
			sum.insert(ptr2.coef, ptr2.power)
			ptr2 = ptr2.next
		return sum.head


class Solution:

	def addPolynomial(self, poly1, poly2):
		p1 = poly1
		p2 = poly2
		ans = dummy = node(0, 0)
		while p1 != None and p2 != None:
			if p1.power == p2.power:
				p1.coef += p2.coef
				dummy.next = p1
				dummy = dummy.next
				p1 = p1.next
				p2 = p2.next
			elif p1.power > p2.power:
				dummy.next = p1
				dummy = dummy.next
				p1 = p1.next
			else:
				dummy.next = p2
				dummy = dummy.next
				p2 = p2.next
		if p1 != None:
			dummy.next = p1
		if p2 != None:
			dummy.next = p2
		return ans.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		if poly1.power >= poly2.power:
			prev = poly1
			head = poly1
			ans = poly1
			curr = poly2
		else:
			prev = poly2
			head = poly2
			ans = poly2
			curr = poly1
		while head and curr:
			if head.power > curr.power:
				prev = head
				head = head.next
			elif head.power == curr.power:
				head.coef += curr.coef
				head = head.next
				curr = curr.next
			elif head.power < curr.power:
				node = node(curr.coeff, curr.power)
				nexx = prev.next
				prev.next = node
				node.next = nexx
				curr = curr.next
		if not head:
			while curr:
				prev.next = curr
				prev = prev.next
				curr = curr.next
		return ans


class Solution:

	def addPolynomial(self, poly1, poly2):
		ret = node(0, 0)

		def calculate(head1, head2):
			ret = head = node(0, 0)
			if not head1:
				return head2
			if not head2:
				return head1
			if head1.power == head2.power:
				ret.next = node(head1.coef + head2.coef, head1.power)
				ret = ret.next
				ret.next = calculate(head1.next, head2.next)
			elif head1.power > head2.power:
				ret.next = head1
				ret = ret.next
				ret.next = calculate(head1.next, head2)
			else:
				ret.next = head2
				ret = ret.next
				ret.next = calculate(head1, head2.next)
			return head.next
		ret.next = calculate(poly1, poly2)
		return ret.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		(c1, c2) = (poly1, poly2)
		head = node(0, 0)
		c = head
		while c1 or c2:
			if not c1:
				c.next = c2
				return c
			if not c2:
				c.next = c1
				return c
			if c1.power == c2.power:
				c.next = node(c1.coef + c2.coef, c1.power)
				c1 = c1.next
				c2 = c2.next
			elif c1.power > c2.power:
				c.next = node(c1.coef, c1.power)
				c1 = c1.next
			else:
				c.next = node(c2.coef, c2.power)
				c2 = c2.next
			c = c.next
		return head.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		cur1 = poly1
		cur2 = poly2
		dummy = node(-1, -1)
		cur = dummy
		while cur1 and cur2:
			if cur1.power > cur2.power:
				cur.next = cur1
				cur1 = cur1.next
			elif cur2.power > cur1.power:
				cur.next = cur2
				cur2 = cur2.next
			else:
				sum = cur1.coef + cur2.coef
				newNode = node(sum, cur1.power)
				cur.next = newNode
				cur1 = cur1.next
				cur2 = cur2.next
			cur = cur.next
		if cur1:
			cur.next = cur1
		if cur2:
			cur.next = cur2
		return dummy.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		poly3 = node(0, 0)
		temp1 = poly1
		temp2 = poly2
		temp3 = poly3
		while temp1 != None and temp2 != None:
			if temp1 == None:
				temp3.next = node(temp2.coef, temp2.power)
				temp2 = temp2.next
				temp3 = temp3.next
			elif temp1 != None and temp1.power < temp2.power:
				temp3.next = node(temp2.coef, temp2.power)
				temp2 = temp2.next
				temp3 = temp3.next
			if temp2 == None:
				temp3.next = node(temp1.coef, temp1.power)
				temp3 = temp3.next
				temp1 = temp1.next
			elif temp2 != None and temp1.power > temp2.power:
				temp3.next = node(temp1.coef, temp1.power)
				temp3 = temp3.next
				temp1 = temp1.next
			if temp1 != None and temp2 != None and (temp1.power == temp2.power):
				temp3.next = node(temp1.coef + temp2.coef, temp1.power)
				temp3 = temp3.next
				temp1 = temp1.next
				temp2 = temp2.next
		return poly3.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		tmp1 = poly1
		tmp2 = poly2
		if tmp1.power == tmp2.power:
			head = node(poly1.coef + poly2.coef, poly1.power)
			tmp1 = tmp1.next
			tmp2 = tmp2.next
		elif tmp1.power > tmp2.power:
			head = node(poly1.coef, poly1.power)
			tmp1 = tmp1.next
		else:
			head = node(poly2.coef, poly2.power)
			tmp2 = tmp2.next
		cur = head
		while tmp1 != None and tmp2 != None:
			if tmp1.power == tmp2.power:
				cur.next = node(tmp1.coef + tmp2.coef, tmp1.power)
				tmp1 = tmp1.next
				tmp2 = tmp2.next
			elif tmp1.power > tmp2.power:
				cur.next = node(tmp1.coef, tmp1.power)
				tmp1 = tmp1.next
			else:
				cur.next = node(tmp2.coef, tmp2.power)
				tmp2 = tmp2.next
			cur = cur.next
		while tmp1 != None:
			cur.next = node(tmp1.coef, tmp1.power)
			tmp1 = tmp1.next
			cur = cur.next
		while tmp2 != None:
			cur.next = node(tmp2.coef, tmp2.power)
			tmp2 = tmp2.next
			cur = cur.next
		return head


class node:

	def __init__(self, coeff, pwr):
		self.coef = coeff
		self.next = None
		self.power = pwr

class Linked_List:

	def __init__(self):
		self.head = None

	def insert(self, coeff, pwr):
		if self.head == None:
			self.head = node(coeff, pwr)
		else:
			new_node = node(coeff, pwr)
			temp = self.head
			while temp.next:
				temp = temp.next
			temp.next = new_node

def createList(arr, n):
	lis = Linked_List()
	k = 0
	for i in range(n):
		lis.insert(arr[k], arr[k + 1])
		k += 2
	return lis.head

class Solution:

	def addPolynomial(self, poly1, poly2):
		ans = node(0, 0)
		retAns = ans
		while poly1 and poly2:
			if poly1.power == poly2.power:
				ans.next = node(poly1.coef + poly2.coef, poly1.power)
				(poly1, poly2) = (poly1.next, poly2.next)
			elif poly1.power > poly2.power:
				ans.next = poly1
				poly1 = poly1.next
			else:
				ans.next = poly2
				poly2 = poly2.next
			ans = ans.next
		if poly1:
			ans.next = poly1
		if poly2:
			ans.next = poly2
		return retAns.next
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		poly1 = createList(arr, n)
		n = int(input())
		arr = list(map(int, input().strip().split()))
		poly2 = createList(arr, n)
		sum = Solution().addPolynomial(poly1, poly2)
		ptr = sum
		while ptr is not None:
			print(str(ptr.coef) + 'x^' + str(ptr.power), end='')
			ptr = ptr.next
			if ptr is not None:
				print(' +', end=' ')
		print()


class node:

	def __init__(self, coeff, pwr):
		self.coef = coeff
		self.next = None
		self.power = pwr

class Linked_List:

	def __init__(self):
		self.head = None

	def insert(self, coeff, pwr):
		if self.head == None:
			self.head = node(coeff, pwr)
		else:
			new_node = node(coeff, pwr)
			temp = self.head
			while temp.next:
				temp = temp.next
			temp.next = new_node

def createList(arr, n):
	lis = Linked_List()
	k = 0
	for i in range(n):
		lis.insert(arr[k], arr[k + 1])
		k += 2
	return lis.head

class Node:

	def __init__(self, coeff, pwr):
		self.coef = coeff
		self.next = None
		self.power = pwr

class Linkedlist:

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

	def insert(self, c, p):
		if self.head == None:
			self.head = Node(c, p)
			self.tail = self.head
		else:
			newnode = Node(c, p)
			self.tail.next = newnode
			self.tail = newnode

class Solution:

	def addPolynomial(self, poly1, poly2):
		l = Linkedlist()
		while poly1 or poly2:
			if poly1 and poly2:
				if poly1.power == poly2.power:
					l.insert(poly1.coef + poly2.coef, poly1.power)
					poly1 = poly1.next
					poly2 = poly2.next
				elif poly1.power > poly2.power:
					l.insert(poly1.coef, poly1.power)
					poly1 = poly1.next
				else:
					l.insert(poly2.coef, poly2.power)
					poly2 = poly2.next
			elif poly1:
				l.tail.next = poly1
				break
			else:
				l.tail.next = poly2
				break
		return l.head
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		poly1 = createList(arr, n)
		n = int(input())
		arr = list(map(int, input().strip().split()))
		poly2 = createList(arr, n)
		sum = Solution().addPolynomial(poly1, poly2)
		ptr = sum
		while ptr is not None:
			print(str(ptr.coef) + 'x^' + str(ptr.power), end='')
			ptr = ptr.next
			if ptr is not None:
				print(' +', end=' ')
		print()


class node:

	def __init__(self, coeff, pwr):
		self.coef = coeff
		self.next = None
		self.power = pwr

class Linked_List:

	def __init__(self):
		self.head = None

	def insert(self, coeff, pwr):
		if self.head == None:
			self.head = node(coeff, pwr)
		else:
			new_node = node(coeff, pwr)
			temp = self.head
			while temp.next:
				temp = temp.next
			temp.next = new_node

def createList(arr, n):
	lis = Linked_List()
	k = 0
	for i in range(n):
		lis.insert(arr[k], arr[k + 1])
		k += 2
	return lis.head

class Solution:

	def addPolynomial(self, poly1, poly2):
		d = {}
		p = poly1
		while True:
			d[p.power] = p.coef
			if p.next:
				p = p.next
			else:
				break
		p = poly2
		while True:
			d[p.power] = d.get(p.power, 0) + p.coef
			if p.next:
				p = p.next
			else:
				break
		k = sorted(d.keys())
		c = k.pop()
		a = node(d[c], c)
		n = a
		while k:
			c = k.pop()
			n.next = node(d[c], c)
			n = n.next
		return a
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		poly1 = createList(arr, n)
		n = int(input())
		arr = list(map(int, input().strip().split()))
		poly2 = createList(arr, n)
		sum = Solution().addPolynomial(poly1, poly2)
		ptr = sum
		while ptr is not None:
			print(str(ptr.coef) + 'x^' + str(ptr.power), end='')
			ptr = ptr.next
			if ptr is not None:
				print(' +', end=' ')
		print()


class Solution:

	def addPolynomial(self, poly1, poly2):
		if poly1 is None and poly2 is None:
			return None
		if poly1 is not None and poly2 is None:
			return poly1
		if poly1 is None and poly2 is not None:
			return poly2
		if poly1.power > poly2.power:
			head = poly1
			tail = poly1
			poly1 = poly1.next
		elif poly1.power < poly2.power:
			head = poly2
			tail = poly2
			poly2 = poly2.next
		elif poly1.power == poly2.power:
			head = poly1
			head.coef += poly2.coef
			tail = poly1
			poly1 = poly1.next
			poly2 = poly2.next
		while poly1 is not None and poly2 is not None:
			if poly1.power > poly2.power:
				tail.next = poly1
				poly1 = poly1.next
				tail = tail.next
			elif poly1.power < poly2.power:
				tail.next = poly2
				tail = tail.next
				poly2 = poly2.next
			elif poly1.power == poly2.power:
				tail.next = poly1
				tail = tail.next
				tail.coef += poly2.coef
				poly1 = poly1.next
				poly2 = poly2.next
		if poly1 is not None:
			tail.next = poly1
		if poly2 is not None:
			tail.next = poly2
		return head


class Solution:

	def addPolynomial(self, poly1, poly2):
		maxPoly = None
		minPoly = None
		resPoly = node(-1, -1)
		temp = resPoly
		while poly1 and poly2:
			if poly1.power == poly2.power:
				temp.next = node(poly1.coef + poly2.coef, poly1.power)
				temp = temp.next
				poly1 = poly1.next
				poly2 = poly2.next
			elif poly1.power > poly2.power:
				temp.next = node(poly1.coef, poly1.power)
				temp = temp.next
				poly1 = poly1.next
			else:
				temp.next = node(poly2.coef, poly2.power)
				temp = temp.next
				poly2 = poly2.next
		while poly1:
			temp.next = node(poly1.coef, poly1.power)
			temp = temp.next
			poly1 = poly1.next
		while poly2:
			temp.next = node(poly2.coef, poly2.power)
			temp = temp.next
			poly2 = poly2.next
		return resPoly.next


class Solution:

	def addPolynomial(self, poly1, poly2):
		if poly1.power == poly2.power:
			nh = node(poly1.coef + poly2.coef, poly1.power)
			poly1 = poly1.next
			poly2 = poly2.next
		elif poly1.power > poly2.power:
			nh = node(poly1.coef, poly1.power)
			poly1 = poly1.next
		else:
			nh = node(poly2.coef, poly2.power)
			poly2 = poly2.next
		p = nh
		while poly1 != None and poly2 != None:
			if poly1.power == poly2.power:
				p.next = node(poly1.coef + poly2.coef, poly1.power)
				poly1 = poly1.next
				poly2 = poly2.next
			elif poly1.power > poly2.power:
				p.next = node(poly1.coef, poly1.power)
				poly1 = poly1.next
			else:
				p.next = node(poly2.coef, poly2.power)
				poly2 = poly2.next
			p = p.next
		while poly1 != None:
			p.next = node(poly1.coef, poly1.power)
			poly1 = poly1.next
			p = p.next
		while poly2 != None:
			p.ext = node(poly2.coef, poly2.power)
			poly2 = poly2.next
			p = p.next
		return nh


class Solution:

	def addPolynomial(self, poly1, poly2):
		if poly1 is None:
			return poly2
		if poly2 is None:
			return poly1
		(ptr1, ptr2) = (poly1, poly2)
		ptrHead = ptrTail = node(0, 0)
		while ptr1 and ptr2:
			if ptr1.power == ptr2.power:
				newNode = ptr1
				newNode.coef += ptr2.coef
				ptr1 = ptr1.next
				ptr2 = ptr2.next
			elif ptr1.power > ptr2.power:
				newNode = ptr1
				ptr1 = ptr1.next
			else:
				newNode = ptr2
				ptr2 = ptr2.next
			ptrTail.next = newNode
			ptrTail = newNode
		if ptr1:
			ptrTail.next = ptr1
		if ptr2:
			ptrTail.next = ptr2
		return ptrHead.next


class Solution:

	def recursion(self, poly1, poly2):
		if not poly1 and (not poly2):
			return
		if not poly1:
			poly1.next = poly2
			return
		elif not poly2:
			return
		if poly1.power > poly2.power:
			return self.recursion(poly1.next, poly2)
		elif poly1.power < poly2.power:
			temp = node(poly1.coef, poly1.power)
			temp.next = poly1.next
			(poly1.coef, poly1.power) = (poly2.coef, poly2.power)
			poly1.next = temp
			return self.recursion(temp, poly2.next)
		else:
			poly1.coef += poly2.coef
			return self.recursion(poly1.next, poly2.next)

	def addPolynomial(self, poly1, poly2):
		self.recursion(poly1, poly2)
		return poly1


class Solution:

	def addPolynomial(self, poly1, poly2):
		l1 = poly1
		l2 = poly2
		ans = None
		while l1 and l2:
			if l1.power > l2.power:
				if ans:
					ans.next = l1
					ans = ans.next
				else:
					ans = l1
					ansh = l1
				l1 = l1.next
			elif l1.power < l2.power:
				if ans:
					ans.next = l2
					ans = ans.next
				else:
					ans = l2
					ansh = l2
				l2 = l2.next
			else:
				l1.coef += l2.coef
				if ans:
					ans.next = l1
					ans = ans.next
				else:
					ans = l1
					ansh = l1
				l1 = l1.next
				l2 = l2.next
		if l1:
			ans.next = l1
		elif l2:
			ans.next = l2
		else:
			ans.next = None
		return ansh


class Solution:

	def addPolynomial(self, poly1, poly2):
		if poly1.power > poly2.power:
			head = poly1
			poly1 = poly1.next
		elif poly2.power > poly1.power:
			head = poly2
			poly2 = poly2.next
		else:
			poly1.coef += poly2.coef
			head = poly1
			poly1 = poly1.next
			poly2 = poly2.next
		ans = head
		(one, two) = (poly1, poly2)
		while one and two:
			if one.power > two.power:
				head.next = one
				one = one.next
			elif two.power > one.power:
				head.next = two
				two = two.next
			else:
				one.coef += two.coef
				head.next = one
				one = one.next
				two = two.next
			head = head.next
		if one:
			head.next = one
		if two:
			head.next = two
		return ans


class Solution:

	def mergeIterative(self, a, b):
		prev = None
		head = None
		c1 = a
		c2 = b
		while c1 and c2:
			if c1.power < c2.power:
				if prev is None:
					head = c2
				else:
					prev.next = c2
				prev = c2
				c2 = c2.next
			elif c1.power > c2.power:
				if prev is None:
					head = c1
				else:
					prev.next = c1
				prev = c1
				c1 = c1.next
			else:
				if prev is None:
					head = c1
				else:
					prev.next = c1
				prev = c1
				c1.coef += c2.coef
				c1 = c1.next
				c2 = c2.next
		if c1:
			prev.next = c1
		if c2:
			prev.next = c2
		return head

	def addPolynomial(self, poly1, poly2):
		return self.mergeIterative(poly1, poly2)