Given two linked lists of size N and M, which are sorted in non-decreasing order. The task is to merge them in such a way that the resulting list is in decreasing order.
Input:
First line of input contains number of testcases T. For each testcase, first line of input conatains length of both linked lists N and M respectively. Next two lines contains N and M elements of two linked lists.
Output:
For each testcase, print the merged linked list which is in non-increasing order.
User Task:
The task is to complete the function mergeResult() which takes reference to the heads of both linked list and returns the pointer to the merged linked list.
Constraints:
1 <=T<= 50
1 <= N, M <= 1000
Example:
Input:
2
4 3
5 10 15 40 
2 3 20
2 2
1 1
2 4 
Output:
40 20 15 10 5 3 2
4 2 1 1 
Explanation:
Testcase 1: After merging the two lists in decreasing order, we have new lists as 40->20->15->10->5->3->2.

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: #User function Template for python3

'''
class Node:
    def __init__(self,data):
        self.data=data
        self.next=None
'''
def mergeResult(h1,h2):
    #return head of merged list

Solutions:
def mergeResult(h1, h2):
	p = h1
	q = h2
	new_head = Node(-99)
	new_head.next = None
	s = None
	if p is None:
		return reverse(q)
	if q is None:
		return reverse(p)
	if p and q:
		if p.data <= q.data:
			s = p
			p = s.next
		else:
			s = q
			q = s.next
	new_head = s
	while p and q:
		if p.data <= q.data:
			s.next = p
			s = p
			p = s.next
		else:
			s.next = q
			s = q
			q = s.next
	if p is None:
		s.next = q
	if q is None:
		s.next = p
	return reverse(new_head)

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


def mergeResult(h1, h2):
	l = []
	while h1 or h2:
		if h1:
			l.append(h1.data)
			h1 = h1.next
		if h2:
			l.append(h2.data)
			h2 = h2.next
	l = sorted(l, reverse=True)
	for i in l:
		print(i, end=' ')


def mergeResult(h1, h2):
	l1 = []
	l2 = []
	while h1:
		l1.append(h1.data)
		h1 = h1.next
	while h2:
		l2.append(h2.data)
		h2 = h2.next
	l1 = l1 + l2
	l1 = sorted(l1)
	l1.reverse()
	head = Node(l1[0])
	t = head
	for j in range(1, len(l1)):
		x = Node(l1[j])
		head.next = x
		head = head.next
	return t


class N:

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

class ls:

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

	def append(self, n_node):
		if self.head == None:
			self.head = N(n_node)
			self.tail = self.head
		else:
			self.tail.next = N(n_node)
			self.tail = self.tail.next

def mergeResult(h1, h2):
	l = []
	while h1:
		l.append(h1.data)
		h1 = h1.next
	while h2:
		l.append(h2.data)
		h2 = h2.next
	l.sort()
	l.reverse()
	ll = ls()
	for i in range(len(l)):
		ll.append(l[i])
	return ll.head


def mergeResult(h1, h2):
	a = []
	b = []
	while h1 != None:
		a.append(h1.data)
		h1 = h1.next
	while h2 != None:
		b.append(h2.data)
		h2 = h2.next
	c = a + b
	c.sort()
	e = c[::-1]
	for j in e:
		print(j, end=' ')


def mergeResult(h1, h2):
	res = []
	while h1 or h2:
		if h1:
			res.append(h1.data)
			h1 = h1.next
		if h2:
			res.append(h2.data)
			h2 = h2.next
	res = sorted(res)[::-1]
	curr = dummy = Node(0)
	for I in res:
		curr.next = Node(I)
		curr = curr.next
	return dummy.next


def mergeResult(h1, h2):
	p = []
	a = h1
	b = h2
	while a is not None:
		p.append(a.data)
		a = a.next
	while b is not None:
		p.append(b.data)
		b = b.next
	q = sorted(p)[::-1]
	h3 = None
	c = None
	for i in q:
		m = Node(i)
		if h3 is None:
			h3 = m
			c = h3
		else:
			c.next = m
			c = c.next
	return h3


def mergeResult(h1, h2):
	result = None
	while h1 and h2:
		if h1.data <= h2.data:
			temp = h1.next
			h1.next = result
			result = h1
			h1 = temp
		else:
			temp = h2.next
			h2.next = result
			result = h2
			h2 = temp
	while h1:
		temp = h1.next
		h1.next = result
		result = h1
		h1 = temp
	while h2:
		temp = h2.next
		h2.next = result
		result = h2
		h2 = temp
	return result


def mergeResult(h1, h2):
	p = h1
	q = h2
	sorted_ptr = p
	llist = Llist()
	while p and q:
		if p.data < q.data:
			p_right = p.next
			p.next = llist.head
			llist.head = p
			p = p_right
		else:
			q_right = q.next
			q.next = llist.head
			llist.head = q
			q = q_right
	if q is None:
		prev = None
		last = p
		while p:
			p_next = p.next
			p.next = prev
			prev = p
			p = p_next
		last.next = llist.head
		llist.head = prev
	else:
		prev = None
		last = q
		while q:
			q_next = q.next
			q.next = prev
			prev = q
			q = q_next
		last.next = llist.head
		llist.head = prev
	return llist.head


def mergeResult(h1, h2):
	a = []
	b = []
	while h1:
		a.append(h1.data)
		h1 = h1.next
	while h2:
		a.append(h2.data)
		h2 = h2.next
	s = sorted(a + b)[::-1]
	dummy = Node(-1)
	p = dummy
	i = 0
	while i < len(s):
		dummy.next = Node(s[i])
		dummy = dummy.next
		i = i + 1
	return p.next


def mergeResult(h1, h2):
	s = []
	temp1 = h1
	temp2 = h2
	while temp1:
		s.append(temp1.data)
		temp1 = temp1.next
	while temp2:
		s.append(temp2.data)
		temp2 = temp2.next
	s = sorted(s)
	for i in s[::-1]:
		print(i, end=' ')


def mergeResult(h1, h2):
	l1 = []
	while h1:
		l1.append(h1.data)
		h1 = h1.next
	while h2:
		l1.append(h2.data)
		h2 = h2.next
	l1.sort()
	res = l1[::-1]
	cur = dummy = Node(0)
	for e in res:
		cur.next = Node(e)
		cur = cur.next
	return dummy.next


def mergeResult(h1, h2):
	l = []
	k = []
	while h1:
		l.append(h1.data)
		h1 = h1.next
	while h2:
		k.append(h2.data)
		h2 = h2.next
	result = []
	i = 0
	j = 0
	while i < len(l) and j < len(k):
		if l[i] <= k[j]:
			result.append(l[i])
			i = i + 1
		else:
			result.append(k[j])
			j = j + 1
	result += l[i:]
	result += k[j:]
	temp = new = Node(0)
	for i in result[::-1]:
		temp.next = Node(i)
		temp = temp.next
	return new.next


def mergeResult(h1, h2):
	l = []
	k = []
	while h1:
		l.append(h1.data)
		h1 = h1.next
	while h2:
		k.append(h2.data)
		h2 = h2.next
	for i in l:
		k.append(i)
	a = sorted(k)
	temp = new = Node(0)
	for i in a[::-1]:
		temp.next = Node(i)
		temp = temp.next
	return new.next


def reverseList(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

def mergeResult(head1, head2):
	if head1.data > head2.data:
		p = head2
		end = head2
		store = head1
	else:
		p = head1
		end = head1
		store = head2
	while True:
		if p.next == None:
			break
		if p.next.data < store.data:
			p = p.next
		else:
			temp = p.next
			p.next = store
			store = temp
			p = p.next
		if p.next == None:
			break
	p.next = store
	ans = reverseList(end)
	return ans


def mergeResult(h1, h2):
	n = h1
	m = h2
	(p, headp) = (None, None)
	while n != None and m != None:
		if n.data <= m.data:
			if p == None:
				p = n
				headp = n
			else:
				p.next = n
				p = p.next
			n = n.next
		else:
			if p == None:
				p = m
				headp = m
			else:
				p.next = m
				p = p.next
			m = m.next
	if n != None:
		p.next = n
		p = p.next
	elif m != None:
		p.next = m
		p = p.next
	else:
		p.next = None

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


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

def mergeResult(h1, h2):
	h1 = reverseList(h1)
	h2 = reverseList(h2)
	dummy = Node(0)
	tail = dummy
	while h1 and h2:
		if h1.data >= h2.data:
			tail.next = h1
			h1 = h1.next
		else:
			tail.next = h2
			h2 = h2.next
		tail = tail.next
	while h1:
		tail.next = h1
		h1 = h1.next
		tail = tail.next
	while h2:
		tail.next = h2
		h2 = h2.next
		tail = tail.next
	return dummy.next


def mergeResult(h1, h2):
	arr = []
	while h1 is not None and h2 is not None:
		if h1.data <= h2.data:
			arr.append(h1.data)
			h1 = h1.next
		else:
			arr.append(h2.data)
			h2 = h2.next
	while h1 is not None:
		arr.append(h1.data)
		h1 = h1.next
	while h2 is not None:
		arr.append(h2.data)
		h2 = h2.next
	head = Node(arr[-1])
	temp = head
	for i in range(len(arr) - 2, -1, -1):
		x = Node(arr[i])
		temp.next = x
		temp = temp.next
	return head


def mergeResult(h1, h2):
	l = []
	while h1:
		k = h1.data
		l.append(k)
		h1 = h1.next
	while h2:
		k = h2.data
		l.append(k)
		h2 = h2.next
	ll = Llist()
	t = None
	l = sorted(l, reverse=True)
	for i in l:
		t = ll.insert(i, t)
	return ll.head


def mergeResult(h1, h2):
	main = []
	while h1 != None:
		main.append(h1.data)
		h1 = h1.next
	while h2 != None:
		main.append(h2.data)
		h2 = h2.next
	main.sort(reverse=True)
	return Node(' '.join(map(str, main)))


def mergeResult(h1, h2):
	x = []
	while h1:
		x.append(h1.data)
		h1 = h1.next
	while h2:
		x.append(h2.data)
		h2 = h2.next
	x.sort(reverse=True)
	a = b = Node(0)
	for i in x:
		a.next = Node(i)
		a = a.next
	return b.next


def mergeResult(h1, h2):
	if h1 == None and h2 == None:
		return None
	res = None
	while h1 != None and h2 != None:
		if h1.data <= h2.data:
			temp = h1.next
			h1.next = res
			res = h1
			h1 = temp
		else:
			temp = h2.next
			h2.next = res
			res = h2
			h2 = temp
	while h2 != None:
		temp = h2.next
		h2.next = res
		res = h2
		h2 = temp
	while h1 != None:
		temp = h1.next
		h1.next = res
		res = h1
		h1 = temp
	return res
	cur = res
	temp = None
	prev = None
	while cur != None:
		temp = cur.next
		cur.next = prev
		prev = cur
		cur = temp
	res = prev
	return rev


def mergeResult(head1, head2):
	l1 = []
	l2 = []
	l3 = []
	c1 = 0
	c2 = 0
	cur1 = Node(head1)
	cur1.data = head1.data
	cur1.next = head1.next
	while cur1 != None:
		l1.append(cur1.data)
		c1 += 1
		cur1 = cur1.next
	cur2 = Node(head2)
	cur2.data = head2.data
	cur2.next = head2.next
	while cur2 != None:
		l2.append(cur2.data)
		c2 += 1
		cur2 = cur2.next
	l3 = l1 + l2
	l3.sort(reverse=True)
	cur = Node(l3[0])
	cur.next = None
	head3 = Node(0)
	head3 = cur
	i = 1
	while i < len(l3):
		new_node = Node(l3[i])
		cur.next = new_node
		cur = cur.next
		i += 1
	return head3


def mergeResult(h1, h2):
	l = []
	while h1 != None:
		l.append(h1.data)
		h1 = h1.next
	while h2 != None:
		l.append(h2.data)
		h2 = h2.next
	l = sorted(l, reverse=True)
	ans = Node(l[0])
	temp = ans
	for i in range(1, len(l)):
		ans.next = Node(l[i])
		ans = ans.next
	return temp


def mergeResult(h1, h2):
	arr = []
	while h1 and h2:
		if h1.data < h2.data:
			arr.append(h1.data)
			h1 = h1.next
		else:
			arr.append(h2.data)
			h2 = h2.next
	while h1:
		arr.append(h1.data)
		h1 = h1.next
	while h2:
		arr.append(h2.data)
		h2 = h2.next
	start = Node(arr.pop())
	head = start
	while arr:
		head.next = Node(arr.pop())
		head = head.next
	head.next = None
	return start


def mergeResult(h1, h2):
	resultHead = None
	while h1 is not None and h2 is not None:
		if h1.data < h2.data:
			node = Node(h1.data)
			h1 = h1.next
		else:
			node = Node(h2.data)
			h2 = h2.next
		node.next = resultHead
		resultHead = node
	while h1 is not None:
		node = Node(h1.data)
		node.next = resultHead
		h1 = h1.next
		resultHead = node
	while h2 is not None:
		node = Node(h2.data)
		node.next = resultHead
		resultHead = node
		h2 = h2.next
	return resultHead


def mergeResult(h1, h2):
	tek1 = h1
	arr = []
	while tek1 != None:
		arr.append(tek1.data)
		tek1 = tek1.next
	tek2 = h2
	while tek2 != None:
		arr.append(tek2.data)
		tek2 = tek2.next
	arr.sort()
	arr.reverse()
	h3 = Node(0)
	tek = h3
	i = 0
	while i < len(arr):
		tek.next = Node(arr[i])
		tek = tek.next
		i += 1
	return h3.next


def mergeResult(h1, h2):

	def reverse(h):
		(prev, cur) = (None, h)
		while cur:
			nxt = cur.next
			cur.next = prev
			prev = cur
			cur = nxt
		return prev
	(h1, h2) = (reverse(h1), reverse(h2))
	dummy = Node(-1)
	tail = dummy
	while h1 and h2:
		if h1.data >= h2.data:
			tail.next = h1
			h1 = h1.next
		else:
			tail.next = h2
			h2 = h2.next
		tail = tail.next
	if h1:
		tail.next = h1
	if h2:
		tail.next = h2
	return dummy.next


def mergeResult(h1, h2):
	new = []
	curr = Node(0)
	temp = curr
	tempnode = h1
	while tempnode:
		new.append(tempnode.data)
		tempnode = tempnode.next
	tempnode = h2
	while tempnode:
		new.append(tempnode.data)
		tempnode = tempnode.next
	new.sort()
	new = new[::-1]
	for i in range(len(new)):
		one = Node(new[i])
		temp.next = one
		temp = one
	return curr.next


class llist:

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

	def insert(self, v):
		node = Node(v)
		if not self.head:
			self.head = node
			self.tail = node
		else:
			self.tail.next = node
			self.tail = node

def mergeResult(h1, h2):
	res = []
	cur = h1
	while cur:
		res.append(cur.data)
		cur = cur.next
	cur = h2
	while cur:
		res.append(cur.data)
		cur = cur.next
	dr = sorted(res, reverse=1)
	r1 = llist()
	for i in dr:
		r1.insert(i)
	return r1.head


def mergeResult(h1, h2):
	lst = []
	ptr = h1
	while ptr:
		lst.append(ptr.data)
		ptr = ptr.next
	ptr = h2
	while ptr:
		lst.append(ptr.data)
		ptr = ptr.next
	lst.sort(reverse=True)
	ll = Llist()
	tail = None
	for i in lst:
		tail = ll.insert(i, tail)
	return ll.head


def mergeResult(head1, head2):
	if head1 == None:
		return head2
	if head2 == None:
		return head1
	if head1.data <= head2.data:
		return solve(head1, head2)
	else:
		return solve(head2, head1)

def solve(first, second):
	if first.next == None:
		first.next = second
		return reverse(first)
	curr1 = first
	nxt1 = curr1.next
	curr2 = second
	nxt2 = curr2.next
	while nxt1 != None and curr2 != None:
		if curr2.data >= curr1.data and curr2.data <= nxt1.data:
			curr1.next = curr2
			nxt2 = curr2.next
			curr2.next = nxt1
			curr1 = curr2
			curr2 = nxt2
		else:
			curr1 = nxt1
			nxt1 = nxt1.next
			if nxt1 == None:
				curr1.next = curr2
				return reverse(first)
	return reverse(first)

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


def mergeResult(h1, h2):

	def reverse(head):
		cur = head
		prev = None
		while cur:
			nxt = cur.next
			cur.next = prev
			prev = cur
			cur = nxt
		return prev
	p = h1
	q = h2
	dummy = Node(-1)
	temp = dummy
	while p or q:
		if p is None:
			temp.next = q
			break
		elif q is None:
			temp.next = p
			break
		elif p.data <= q.data:
			temp.next = p
			temp = temp.next
			p = p.next
		elif p.data > q.data:
			temp.next = q
			temp = temp.next
			q = q.next
	return reverse(dummy.next)


def mergeResult(h1, h2):
	new_node = Node(0)
	x = []
	curr1 = h1
	curr2 = h2
	tmp_node = new_node
	while curr1:
		x.append(curr1.data)
		curr1 = curr1.next
	while curr2:
		x.append(curr2.data)
		curr2 = curr2.next
	for node in sorted(x)[::-1]:
		tmp_node.next = Node(node)
		tmp_node = tmp_node.next
	return new_node.next


def mergeResult(h1, h2):
	head = Node(-1)
	prev = head
	while h1 and h2:
		if h1.data >= h2.data:
			temp = Node(h2.data)
			prev.next = temp
			prev = temp
			h2 = h2.next
		elif h1.data <= h2.data:
			temp = Node(h1.data)
			prev.next = temp
			prev = temp
			h1 = h1.next
	if h1 == None:
		prev.next = h2
	else:
		prev.next = h1
	head = head.next
	ans = reverse(head)
	return ans

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


def mergeResult(h1, h2):
	dummy = Node(-1)
	head1 = h1
	head2 = h2
	head = dummy
	while head1 and head2:
		if head1.data <= head2.data:
			new = Node(head1.data)
			head.next = new
			head = head.next
			head1 = head1.next
		else:
			new = Node(head2.data)
			head.next = new
			head = head.next
			head2 = head2.next
	if head1 != None:
		head.next = head1
	else:
		head.next = head2
	ans = dummy.next
	dummy.next = None
	ans = reverse(ans)
	return ans

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


def merge(h3, h4):
	if h3.next is None:
		h3.next = h4
		return h3
	temp1 = h3
	nxt1 = h3.next
	temp2 = h4
	nxt2 = h4.next
	while nxt1 != None and temp2 != None:
		if temp2.data >= temp1.data and temp2.data <= nxt1.data:
			temp1.next = temp2
			nxt2 = temp2.next
			temp2.next = nxt1
			temp1 = temp2
			temp2 = nxt2
		else:
			temp1 = nxt1
			nxt1 = nxt1.next
			if nxt1 is None:
				temp1.next = temp2
				return h3
	return h3

def reverse(curr):
	if curr is None:
		return -1
	if curr.next is None:
		return curr
	prev = None
	nxt = None
	temp = curr
	while temp:
		nxt = temp.next
		temp.next = prev
		prev = temp
		temp = nxt
	return prev

def mergeResult(h1, h2):
	if h1 is None:
		return h2
	if h2 is None:
		return h1
	if h1.data <= h2.data:
		curr = merge(h1, h2)
		return reverse(curr)
	elif h1.data > h2.data:
		curr = merge(h2, h1)
		return reverse(curr)


def mergeResult(h1, h2):
	temp = h1
	anslist = []
	while temp != None:
		anslist.append(temp.data)
		temp = temp.next
	temp = h2
	while temp != None:
		anslist.append(temp.data)
		temp = temp.next
	anslist.sort()
	temp = Node(anslist.pop())
	res = temp
	while anslist:
		temp1 = Node(anslist.pop())
		temp.next = temp1
		temp = temp.next
	return res


def mergeResult(h1, h2):
	a = []
	b = []
	while h1 is not None:
		a.append(h1.data)
		h1 = h1.next
	while h2 is not None:
		b.append(h2.data)
		h2 = h2.next
	s = a + b
	s.sort()
	s = s[::-1]
	for i in s:
		print(i, end=' ')


def mergeResult(h1, h2):
	l = []
	while h1:
		l.append(h1.data)
		h1 = h1.next
	while h2:
		l.append(h2.data)
		h2 = h2.next
	l.sort()
	l = l[::-1]
	a = Node(0)
	t = a
	for i in l:
		t.next = Node(i)
		t = t.next
	return a.next


def mergeResult(h1, h2):
	a = []
	b = []
	f = h1
	g = h2
	while f:
		a.append(f.data)
		f = f.next
	while g:
		b.append(g.data)
		g = g.next
	k = a + b
	k.sort()
	d = k[::-1]
	w = q = Node(d[0])
	for i in range(1, len(d)):
		w.next = Node(d[i])
		w = w.next
	return q


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

def mergeResult(h1, h2):
	res = Node(0)
	resh = res
	a = -1
	b = -1
	while h1 or h2:
		if h1 and h2:
			a = h1.data
			b = h2.data
			if a >= b:
				res.next = Node(b)
				res = res.next
				h2 = h2.next
			else:
				res.next = Node(a)
				res = res.next
				h1 = h1.next
		elif h1 and (not h2):
			res.next = h1
			break
		elif not h1 and h2:
			res.next = h2
			break
	return reverseLL(resh.next)


def mergeResult(h1, h2):
	ptr1 = h1
	ptr2 = h2
	l1 = []
	l2 = []
	while ptr1:
		l1.append(ptr1.data)
		ptr1 = ptr1.next
	while ptr2:
		l2.append(ptr2.data)
		ptr2 = ptr2.next
	l3 = l1 + l2
	l3.sort(reverse=True)
	dummy = Node(0)
	n0 = dummy
	for i in l3:
		n0.next = Node(i)
		n0 = n0.next
	return dummy.next


def mergeResult(h1, h2):
	a = []
	while h1:
		a.append(h1.data)
		h1 = h1.next
	while h2:
		a.append(h2.data)
		h2 = h2.next
	a.sort()
	a.reverse()
	dummy = Node(-1)
	move = dummy
	for i in a:
		new = Node(i)
		move.next = new
		move = move.next
	return dummy.next


def mergeResult(h1, h2):
	dummy = Node(0)
	new = dummy
	(ptr1, ptr2) = (h1, h2)
	while ptr1 and ptr2:
		if ptr1.data < ptr2.data:
			dummy.next = ptr1
			ptr1 = ptr1.next
			dummy = dummy.next
		else:
			dummy.next = ptr2
			ptr2 = ptr2.next
			dummy = dummy.next
	if ptr1:
		dummy.next = ptr1
	elif ptr2:
		dummy.next = ptr2
	(curr, prev) = (new.next, None)
	while curr:
		nxt = curr.next
		curr.next = prev
		prev = curr
		curr = nxt
	return prev


def mergeResult(h1, h2):
	b = []
	tmp1 = h1
	tmp2 = h2
	while tmp1.next != None:
		b.append(tmp1.data)
		tmp1 = tmp1.next
	b.append(tmp1.data)
	tmp1.next = h2
	while tmp2 != None:
		b.append(tmp2.data)
		tmp2 = tmp2.next
	b.sort()
	tmp1 = h1
	for i in reversed(b):
		tmp1.data = i
		tmp1 = tmp1.next
	return h1


def mergeResult(h1, h2):
	(s, p) = ([], [])
	while h1:
		s.append(h1.data)
		h1 = h1.next
	while h2:
		p.append(h2.data)
		h2 = h2.next
	for i in p:
		s.append(i)
	s[::-1] = sorted(s)
	for i in s:
		print(i, end=' ')


def mergeResult(h1, h2):
	l = []
	while h1:
		l.append(h1.data)
		h1 = h1.next
	while h2:
		l.append(h2.data)
		h2 = h2.next
	l.sort()
	head = Node(l[0])
	for item in l[1:]:
		new_node = Node(item)
		if head is None:
			head = new_node
			new_node.next = None
		else:
			new_node.next = head
			head = new_node
	return head


class Node:

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

def mergeResult(h1, h2):
	cur1 = h1
	cur2 = h2
	dummy = Node(0)
	cur3 = dummy
	while cur1 and cur2:
		if cur1.data <= cur2.data:
			cur3.next = cur1
			cur1 = cur1.next
		else:
			cur3.next = cur2
			cur2 = cur2.next
		cur3 = cur3.next
	while cur1:
		cur3.next = cur1
		cur1 = cur1.next
		cur3 = cur3.next
	while cur2:
		cur3.next = cur2
		cur2 = cur2.next
		cur3 = cur3.next
	pre = None
	cur = dummy.next
	while cur:
		temp = cur.next
		cur.next = pre
		pre = cur
		cur = temp
	return pre


def mergeResult(h1, h2):
	dummy = Node(-1)
	temp = dummy
	while h1 and h2:
		if h1.data < h2.data:
			temp.next = h1
			h1 = h1.next
			temp = temp.next
		else:
			temp.next = h2
			h2 = h2.next
			temp = temp.next
	if h1:
		temp.next = h1
	if h2:
		temp.next = h2
	head = dummy.next
	(prev, nxt) = (None, None)
	while head:
		nxt = head.next
		head.next = prev
		prev = head
		head = nxt
	return prev


def mergeResult(h1, h2):
	lst = []
	while h1 != None and h2 != None:
		if h1.data <= h2.data:
			lst.append(h1.data)
			h1 = h1.next
		else:
			lst.append(h2.data)
			h2 = h2.next
	while h1 != None:
		lst.append(h1.data)
		h1 = h1.next
	while h2 != None:
		lst.append(h2.data)
		h2 = h2.next
	lst.reverse()
	newnode = Node(0)
	final = newnode
	for item in lst:
		newnode.next = Node(item)
		newnode = newnode.next
	return final.next


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

def mergeResult(h1, h2):
	if h1 == None:
		return h2
	if h2 == None:
		return h1
	hf = ht = None
	if h1.data <= h2.data:
		hf = ht = h1
		h1 = h1.next
	else:
		ht = hf = h2
		h2 = h2.next
	while h1 and h2:
		if h1.data <= h2.data:
			ht.next = h1
			h1 = h1.next
		else:
			ht.next = h2
			h2 = h2.next
		ht = ht.next
	if h1:
		ht.next = h1
	if h2:
		ht.next = h2
	return reverse(hf)


class Node:

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

def mergeResult(h1, h2):
	c = h1
	d = h2
	a = []
	while c != None:
		a.append(c.data)
		c = c.next
	while d != None:
		a.append(d.data)
		d = d.next
	b = a.sort(reverse=True)
	st = None
	en = None
	for i in a:
		t = Node(i)
		if st == None:
			st = t
			en = t
		else:
			en.next = t
			en = en.next
	return st


def mergeResult(h1, h2):
	r1 = reverseList(h1)
	r2 = reverseList(h2)
	return mergeLists(r1, r2)

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

def mergeLists(head1, head2):
	temp1 = head1
	temp2 = head2
	dummy = Node(0)
	cursor = dummy
	while temp1 or temp2:
		if temp1 and temp2:
			if temp1.data > temp2.data:
				cursor.next = Node(temp1.data)
				cursor = cursor.next
				temp1 = temp1.next
			else:
				cursor.next = Node(temp2.data)
				cursor = cursor.next
				temp2 = temp2.next
		elif temp1:
			cursor.next = Node(temp1.data)
			cursor = cursor.next
			temp1 = temp1.next
		elif temp2:
			cursor.next = Node(temp2.data)
			cursor = cursor.next
			temp2 = temp2.next
	return dummy.next

def display(head):
	temp = head
	a = []
	while temp:
		a.append(str(temp.data))
		temp = temp.next
	return ' '.join(a)


def traverse_list(h1):
	l1 = 0
	arr1 = []
	while h1.next != None:
		arr1.append(h1.data)
		l1 += 1
		h1 = h1.next
	arr1.append(h1.data)
	l1 += 1
	return (arr1, l1)

def mergeResult(h1, h2):
	(arr1, l1) = traverse_list(h1)
	(arr2, l2) = traverse_list(h2)
	left_ptr = l1 - 1
	right_ptr = l2 - 1
	res = []
	while (left_ptr >= 0) | (right_ptr >= 0):
		if left_ptr == -1:
			res.append(arr2[right_ptr])
			right_ptr -= 1
		elif right_ptr == -1:
			res.append(arr1[left_ptr])
			left_ptr -= 1
		elif arr1[left_ptr] > arr2[right_ptr]:
			res.append(arr1[left_ptr])
			left_ptr -= 1
		else:
			res.append(arr2[right_ptr])
			right_ptr -= 1
	for e in res:
		print(e, end=' ')


def mergeResult(h1, h2):
	head1 = h1
	head2 = h2
	start = None
	i = 0
	j = 0
	final = None
	while head1 and head2:
		if head1.data <= head2.data:
			if not start:
				start = head1
				final = start
			else:
				start.next = head1
				start = start.next
			head1 = head1.next
		else:
			if not start:
				start = head2
				final = start
			else:
				start.next = head2
				start = start.next
			head2 = head2.next
	if not head1:
		start.next = head2
	else:
		start.next = head1
	final = reverse(final)
	return final

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


def mergeResult(h1, h2):
	s = []
	while h1 != None:
		s.append(h1.data)
		h1 = h1.next
	while h2 != None:
		s.append(h2.data)
		h2 = h2.next
	s.sort()
	for i in range(len(s) - 1, -1, -1):
		print(s[i], end=' ')


def mergeResult(h1, h2):
	start1 = h1
	start2 = h2
	result = None
	while start1 or start2:
		currNode = None
		if start1 and start2:
			if start1.data <= start2.data:
				currNode = start1
				start1 = start1.next
			else:
				currNode = start2
				start2 = start2.next
		elif start1 and (not start2):
			currNode = start1
			start1 = start1.next
		else:
			currNode = start2
			start2 = start2.next
		currNode.next = result
		result = currNode
	return result


def mergeResult(list1, list2):
	if list1.data > list2.data:
		temp = list1
		list1 = list2
		list2 = temp
	res = list1
	while list1 != None and list2 != None:
		temp = None
		while list1 != None and list1.data <= list2.data:
			temp = list1
			list1 = list1.next
		temp.next = list2
		t = list2
		list2 = list1
		list1 = t
	t = res
	d = None
	while t != None:
		n = t.next
		t.next = d
		d = t
		t = n
	res = d
	return res


def mergeResult(h1, h2):
	l = []
	if h1:
		temp = h1
		while temp:
			l.append(temp.data)
			temp = temp.next
	if h2:
		temp = h2
		while temp:
			l.append(temp.data)
			temp = temp.next
	l.sort(reverse=True)
	head = None
	tail = None
	while l:
		a = l.pop(0)
		n = Node(a)
		if head == None:
			head = n
			tail = n
		else:
			tail.next = n
			tail = tail.next
	return head


def mergeResult(h1, h2):

	def reverse(n):
		prev = None
		curr = n
		while curr:
			nxt = curr.next
			curr.next = prev
			prev = curr
			curr = nxt
		return prev
	h1 = reverse(h1)
	h2 = reverse(h2)
	dummy = Node(-1)
	tmp = dummy
	while h1 and h2:
		if h1.data > h2.data:
			tmp.next = h1
			h1 = h1.next
		else:
			tmp.next = h2
			h2 = h2.next
		tmp = tmp.next
	if h1:
		tmp.next = h1
	elif h2:
		tmp.next = h2
	return dummy.next


def mergeResult(h1, h2):
	l = []
	c1 = h1
	c2 = h2
	while c1:
		l.append(c1.data)
		c1 = c1.next
	while c2:
		l.append(c2.data)
		c2 = c2.next
	l.sort()
	l.reverse()
	h3 = Node(l[0])
	c3 = h3
	for (i, v) in enumerate(l):
		if i != 0:
			new = Node(v)
			c3.next = new
			c3 = new
	return h3


def mergeResult(h1, h2):
	l = []
	ptr1 = h1
	ptr2 = h2
	while ptr1:
		l.append(ptr1.data)
		ptr1 = ptr1.next
	while ptr2:
		l.append(ptr2.data)
		ptr2 = ptr2.next
	l.sort()
	l.reverse()
	h3 = Node(l[0])
	ptr3 = h3
	for (i, v) in enumerate(l):
		if i != 0:
			new = Node(v)
			ptr3.next = new
			ptr3 = new
	return h3


def mergeResult(h1, h2):
	z1 = []
	while h1 is not None:
		z1.append(h1.data)
		h1 = h1.next
	while h2 is not None:
		z1.append(h2.data)
		h2 = h2.next
	z1.sort()
	z = z1[::-1]
	head = None
	tail = None
	for i in z:
		if i != -1:
			newnode = Node(i)
			if head is None:
				head = newnode
				tail = newnode
			else:
				tail.next = newnode
				tail = newnode
	return head


def mergeResult(h1, h2):
	A = []
	B = []
	while h1:
		A += [h1]
		h1 = h1.next
	while h2:
		B += [h2]
		h2 = h2.next
	A = A + B
	A.sort(key=lambda x: x.data, reverse=True)
	for i in range(len(A) - 1):
		A[i].next = A[i + 1]
	A[-1].next = None
	return A[0]


def mergeResult(h1, h2):
	res = []
	(t1, t2) = (h1, h2)
	while t1:
		res.append(t1.data)
		t1 = t1.next
	while t2:
		res.append(t2.data)
		t2 = t2.next
	res.sort(reverse=True)
	for i in res:
		print(i, end=' ')


def mergeResult(h1, h2):

	def rev(h1):
		curr = h1
		prev = None
		while curr:
			temp = curr.next
			curr.next = prev
			prev = curr
			curr = temp
		return prev
	revhead1 = rev(h1)
	temp1 = revhead1

	def rev(h2):
		current = h2
		previous = None
		while current:
			temp3 = current.next
			current.next = previous
			previous = current
			current = temp3
		return previous
	revhead2 = rev(h2)
	temp2 = revhead2
	dummy = Node(0)
	tail = dummy
	while temp1 is not None and temp2 is not None:
		if temp1.data >= temp2.data:
			tail.next = temp1
			temp1 = temp1.next
		else:
			tail.next = temp2
			temp2 = temp2.next
		tail = tail.next
	if temp1 is None:
		tail.next = temp2
	if temp2 is None:
		tail.next = temp1
	return dummy.next


def mergeResult(h1, h2):
	li = []
	head = None
	while h1:
		li.append(h1.data)
		h1 = h1.next
	while h2:
		li.append(h2.data)
		h2 = h2.next
	li = sorted(li)
	for i in range(len(li)):
		node = Node(li.pop())
		if head == None:
			head = node
			h = head
		else:
			h.next = node
			h = h.next
	return head


def mergeResult(h1, h2):
	a = []
	b = []
	while h1:
		a.append(h1.data)
		h1 = h1.next
	while h2:
		b.append(h2.data)
		h2 = h2.next
	u = a + b
	u = sorted(u)
	h = Node(u[0])
	u.remove(u[0])
	for i in u:
		new_node = Node(i)
		new_node.next = h
		h = new_node
	return h


def mergeResult(h1, h2):
	l = []
	temp = h1
	while temp:
		l.append(temp.data)
		temp = temp.next
	temp = h2
	while temp:
		l.append(temp.data)
		temp = temp.next
	l.sort()
	l3 = None
	for i in l:
		temp = Node(i)
		temp.next = l3
		l3 = temp
	return l3


def mergeResult(h1, h2):

	def reverse(head):
		if head == None:
			return
		prev = None
		currNode = head
		while currNode != None:
			nxt = currNode.next
			currNode.next = prev
			prev = currNode
			currNode = nxt
		return prev

	def merge(h1, h2):
		if h1 == None:
			return h2
		if h2 == None:
			return h1
		dummy = Node(-1)
		h3 = dummy
		while h1 != None and h2 != None:
			if h1.data > h2.data:
				h3.next = h1
				h1 = h1.next
			else:
				h3.next = h2
				h2 = h2.next
			h3 = h3.next
		if h1 != None:
			h3.next = h1
		if h2 != None:
			h3.next = h2
		return dummy.next
	left = reverse(h1)
	right = reverse(h2)
	return merge(left, right)


def mergeResult(h1, h2):
	ll = Llist()
	tail = None
	head1 = h1
	head2 = h2
	while head1 or head2:
		if head1 and head2:
			if head1.data < head2.data:
				tail = ll.insert(head1.data, tail)
				head1 = head1.next
			elif head2.data < head1.data:
				tail = ll.insert(head2.data, tail)
				head2 = head2.next
			elif head1.data == head2.data:
				tail = ll.insert(head1.data, tail)
				tail = ll.insert(head1.data, tail)
				head1 = head1.next
				head2 = head2.next
		elif head1 is not None and head2 is None:
			tail = ll.insert(head1.data, tail)
			head1 = head1.next
		elif head2 is not None and head1 is None:
			tail = ll.insert(head2.data, tail)
			head2 = head2.next
	prev = None
	cur = ll.head
	while cur:
		nextn = cur.next
		cur.next = prev
		prev = cur
		cur = nextn
	ll.head = prev
	return ll.head


def mergeResult(h1, h2):
	d = []
	while h1:
		d.append(h1.data)
		h1 = h1.next
	while h2:
		d.append(h2.data)
		h2 = h2.next
	l = sorted(d, reverse=True)
	n = len(l)
	ans = temp = Node(-1)
	for i in range(n):
		temp.next = Node(l[i])
		temp = temp.next
	return ans.next


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

def mergeResult(h1, h2):
	h1 = reverse(h1)
	h2 = reverse(h2)
	ans = Node(-1)
	temp = ans
	while h1 and h2:
		if h1.data > h2.data:
			temp.next = Node(h1.data)
			temp = temp.next
			h1 = h1.next
		else:
			temp.next = Node(h2.data)
			temp = temp.next
			h2 = h2.next
	while h1:
		temp.next = Node(h1.data)
		temp = temp.next
		h1 = h1.next
	while h2:
		temp.next = Node(h2.data)
		temp = temp.next
		h2 = h2.next
	return ans.next


def mergeResult(h1, h2):
	(t, t1) = (h1, h2)
	k = []
	while t:
		k.append(t.data)
		t = t.next
	while t1:
		k.append(t1.data)
		t1 = t1.next
	k.sort()
	k.reverse()
	i = 1
	head = Node(k[0])
	m = head
	while i < len(k):
		l = Node(k[i])
		m.next = l
		m = m.next
		i += 1
	return head


def mergeResult(h1, h2):
	newHead = None
	tail = None
	data = []
	temp1 = h1
	temp2 = h2
	while temp1 is not None and temp2 is not None:
		if temp1.data <= temp2.data:
			data.append(temp1.data)
			temp1 = temp1.next
		else:
			data.append(temp2.data)
			temp2 = temp2.next
	while temp1 is not None:
		data.append(temp1.data)
		temp1 = temp1.next
	while temp2 is not None:
		data.append(temp2.data)
		temp2 = temp2.next
	for i in range(len(data) - 1, -1, -1):
		node = Node(data[i])
		if newHead is None:
			newHead = node
			tail = newHead
		else:
			tail.next = node
			tail = node
	return newHead


def mergeResult(h1, h2):
	if h1 is None and h2 is None:
		return None
	res = None
	while h1 and h2:
		if h1.data <= h2.data:
			temp = h1.next
			h1.next = res
			res = h1
			h1 = temp
		else:
			temp = h2.next
			h2.next = res
			res = h2
			h2 = temp
	while h1 is not None:
		temp = h1.next
		h1.next = res
		res = h1
		h1 = temp
	while h2 is not None:
		temp = h2.next
		h2.next = res
		res = h2
		h2 = temp
	return res


def mergeResult(h1, h2):
	res = None
	while h1 or h2:
		if h1 and h2:
			a = h1.data if h1 else 0
			b = h2.data if h2 else 0
			if a <= b:
				temp = h1.next
				h1.next = res
				res = h1
				h1 = temp
			else:
				temp = h2.next
				h2.next = res
				res = h2
				h2 = temp
		if h1 and (not h2):
			temp = h1.next
			h1.next = res
			res = h1
			h1 = temp
		if h2 and (not h1):
			temp = h2.next
			h2.next = res
			res = h2
			h2 = temp
	return res


def mergeResult(h1, h2):
	ans = node = Node(-1)
	list1 = []
	while h1 or h2:
		if h1:
			list1.append(h1.data)
			h1 = h1.next
		if h2:
			list1.append(h2.data)
			h2 = h2.next
	list1.sort(reverse=True)
	for i in list1:
		node.next = Node(i)
		node = node.next
	return ans.next


from heapq import heappush, heappop

def mergeResult(list1, list2):
	dummy = Node(-1)
	heap = []
	while list1:
		heappush(heap, -list1.data)
		list1 = list1.next
	while list2:
		heappush(heap, -list2.data)
		list2 = list2.next
	curr = dummy
	while heap:
		temp = Node(-heappop(heap))
		curr.next = temp
		curr = curr.next
	return dummy.next


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

def mergeResult(h1, h2):
	dummy = Node(0)
	M_head = dummy
	h1 = reverse(h1)
	h2 = reverse(h2)
	while h1 and h2:
		if h1.data > h2.data:
			dummy.next = h1
			dummy = dummy.next
			h1 = h1.next
		else:
			dummy.next = h2
			dummy = dummy.next
			h2 = h2.next
	if h1:
		dummy.next = h1
	if h2:
		dummy.next = h2
	return M_head.next


def mergeResult(h1, h2):
	(temp1, temp2) = (h1, h2)
	new_list = Node(None)
	returned_list = new_list
	while temp1 and temp2:
		v1 = temp1.data if temp1 else None
		v2 = temp2.data if temp2 else None
		if v1 > v2:
			new_list.next = Node(v2)
			temp2 = temp2.next
		else:
			new_list.next = Node(v1)
			temp1 = temp1.next
		new_list = new_list.next
	new_list.next = temp1 if temp1 else temp2
	prev = None
	cur = returned_list.next
	while cur:
		nxt = cur.next
		cur.next = prev
		prev = cur
		cur = nxt
	new_head = prev
	return prev


def mergeResult(h1, h2):
	num1 = []
	num2 = []
	t1 = h1
	t2 = h2
	while t1:
		num1.append(t1.data)
		t1 = t1.next
	while t2:
		num2.append(t2.data)
		t2 = t2.next
	num3 = num1 + num2
	num3.sort()
	num3 = num3[::-1]
	r = Llist()
	tail = None
	for i in num3:
		tail = r.insert(i, tail)
	return r.head


def mergeResult(h1, h2):
	n = []
	while h1:
		n.append(h1.data)
		h1 = h1.next
	while h2:
		n.append(h2.data)
		h2 = h2.next
	k = len(n)
	n.sort()
	ans = pre = Node(-1)
	for i in range(k - 1, -1, -1):
		pre.next = Node(n[i])
		pre = pre.next
	return ans.next


def mergeResult(h1, h2):
	s = list()
	while h1:
		s.append(h1.data)
		h1 = h1.next
	while h2:
		s.append(h2.data)
		h2 = h2.next
	head = Node(0)
	extra_node = head
	s = sorted(s, reverse=True)
	for i in s:
		node = Node(i)
		head.next = node
		head = node
	return extra_node.next