Given two sorted linked lists consisting of N and M nodes respectively. The task is to merge both of the list (in-place) and return head of the merged list.
 
Example 1:
Input:
N = 4, M = 3 
valueN[] = {5,10,15,40}
valueM[] = {2,3,20}
Output: 2 3 5 10 15 20 40
Explanation: After merging the two linked
lists, we have merged list as 2, 3, 5,
10, 15, 20, 40.
Example 2:
Input:
N = 2, M = 2
valueN[] = {1,1}
valueM[] = {2,4}
Output:1 1 2 4
Explanation: After merging the given two
linked list , we have 1, 1, 2, 4 as
output.
Your Task:
The task is to complete the function sortedMerge() which takes references to the heads of two linked lists as the arguments and returns the head of merged linked list.
Expected Time Complexity : O(n+m)
Expected Auxilliary Space : O(1)
Constraints:
1 <= N, M <= 10^{4}
0 <= Node's data <= 10^{5}

Difficulty: MEDIUM
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(n+m)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

'''

	Function to merge two sorted lists in one

	using constant space.

	

	Function Arguments: head_a and head_b (head reference of both the sorted lists)

	Return Type: head of the obtained list after merger.



	{

		# Node Class

		class Node:

		    def __init__(self, data):   # data -> value stored in node

		        self.data = data

		        self.next = None

	}



'''

#Function to merge two sorted linked list.

def sortedMerge(head1, head2):

    # code here

Solutions:
def findBetween(a1, a2, b):
	start_b = b
	while b is not None and a1.data <= b.data <= a2.data:
		if b.next is None or b.next.data > a2.data:
			break
		b = b.next
	return (start_b, b)

def sortedMerge(head1, head2):
	temp_node = Node(-1)
	temp_node.next = head1
	(a1, a2, b) = (temp_node, temp_node.next, head2)
	next_b = b
	while a2 is not None and next_b is not None:
		(start_b, b) = findBetween(a1, a2, next_b)
		if a1.data <= start_b.data <= a2.data:
			next_b = b.next
			a1.next = start_b
			b.next = a2
		a1 = a2
		if a2.next is None and next_b is not None:
			a2.next = next_b
			break
		else:
			a2 = a2.next
	return temp_node.next


def sortedMerge(head1, head2):
	res = LinkedList()
	for i in range(n + m):
		if head2 == None or (head1 != None and head1.data <= head2.data):
			res.append(head1.data)
			head1 = head1.next
		else:
			res.append(head2.data)
			head2 = head2.next
	return res.head


def sortedMerge(headN, headM):
	if not headN:
		return headM
	if not headM:
		return headN
	if headN.data <= headM.data:
		head = headN
		curr = headN
		N = headN.next
		M = headM
	else:
		head = headM
		curr = headM
		N = headN
		M = headM.next
	while N is not None and M is not None:
		if N.data <= M.data:
			curr.next = N
			curr = N
			N = N.next
		else:
			temp = M
			M = M.next
			curr.next = temp
			curr = temp
			curr.next = N
	if N is not None:
		curr.next = N
	if M is not None:
		curr.next = M
	return head


def sortedMerge(head1, head2):
	if not head1:
		return head2
	if not head2:
		return head1
	(temp1, temp2) = (head1, head2)
	temp = None
	while temp1 and temp2:
		if temp1.data <= temp2.data:
			if temp:
				temp.next = temp1
			temp = temp1
			temp1 = temp1.next
		else:
			if temp:
				temp.next = temp2
			temp = temp2
			temp2 = temp2.next
	if temp1:
		temp.next = temp1
	if temp2:
		temp.next = temp2
	if head1.data <= head2.data:
		return head1
	return head2


def sortedMerge(head1, head2):
	if head1 == None:
		return head2
	if head2 == None:
		return head1
	if head1.data < head2.data:
		head = tail = head1
		head1 = head1.next
	else:
		head = tail = head2
		head2 = head2.next
	while head1 and head2:
		if head1.data < head2.data:
			tail.next = head1
			tail = head1
			head1 = head1.next
		else:
			tail.next = head2
			tail = head2
			head2 = head2.next
	if head1 == None:
		tail.next = head2
	else:
		tail.next = head1
	return head


def sortedMerge(head1, head2):
	if head1.data < head2.data:
		res = head1
		curr = head1
		head1 = head1.next
	else:
		res = head2
		curr = head2
		head2 = head2.next
	while True:
		if head1 == None:
			curr.next = head2
			return res
		elif head2 == None:
			curr.next = head1
			return res
		if head1.data < head2.data:
			curr.next = head1
			head1 = head1.next
			curr = curr.next
		else:
			curr.next = head2
			head2 = head2.next
			curr = curr.next


def sortedMerge(head1, head2):
	a = []
	while head1:
		a.append(head1.data)
		head1 = head1.next
	while head2:
		a.append(head2.data)
		head2 = head2.next
	a.sort(reverse=True)
	p = None
	for i in a:
		temp = Node(i)
		if p is None:
			p = temp
		else:
			temp.next = p
			p = temp
	return p


def sortedMerge(head1, head2):
	temp1 = head1
	temp2 = head2
	head = None
	curr = None
	while temp1 is not None and temp2 is not None:
		if temp1.data < temp2.data:
			if head is None:
				head = temp1
			else:
				curr.next = temp1
			curr = temp1
			temp1 = temp1.next
		else:
			if head is None:
				head = temp2
			else:
				curr.next = temp2
			curr = temp2
			temp2 = temp2.next
	while temp1 is not None:
		if head is None:
			head = temp1
		else:
			curr.next = temp1
		curr = temp1
		temp1 = temp1.next
	while temp2 is not None:
		if head is None:
			head = temp2
		else:
			curr.next = temp2
		curr = temp2
		temp2 = temp2.next
	return head


def sortedMerge(head1, head2):
	if head1.data <= head2.data:
		final_head = head1
		temp = head1
		i = temp.next
		j = head2
	else:
		final_head = head2
		temp = head2
		i = head1
		j = temp.next
	while i is not None and j is not None:
		if i.data <= j.data:
			temp.next = i
			temp = temp.next
			i = i.next
		else:
			temp.next = j
			temp = temp.next
			j = j.next
	while i is not None:
		temp.next = i
		temp = temp.next
		i = i.next
	while j is not None:
		temp.next = j
		temp = temp.next
		j = j.next
	return final_head


def sortedMerge(head1, head2):
	if not head1 and (not head2):
		return head1
	if not head1:
		return head2
	if not head2:
		return head1
	ans = None
	head = None
	while head1 and head2:
		if head1.data > head2.data:
			if head:
				head.next = head2
				head = head.next
			else:
				head = head2
				ans = head
			head2 = head2.next
		else:
			if head:
				head.next = head1
				head = head.next
			else:
				head = head1
				ans = head
			head1 = head1.next
	if head1:
		head.next = head1
	if head2:
		head.next = head2
	return ans


def sortedMerge(head1, head2):
	if not head1 and (not head2):
		return head1
	if not head1:
		return head2
	if not head2:
		return head1
	dummy = Node(-1)
	head = dummy
	while head1 and head2:
		if head1.data > head2.data:
			head.next = head2
			head2 = head2.next
			head = head.next
		else:
			head.next = head1
			head1 = head1.next
			head = head.next
	if head1:
		head.next = head1
	if head2:
		head.next = head2
	return dummy.next


def sortedMerge(headA, headB):
	dummyNode = Node(0)
	tail = dummyNode
	while True:
		if headA is None:
			tail.next = headB
			break
		if headB is None:
			tail.next = headA
			break
		if headA.data <= headB.data:
			tail.next = headA
			headA = headA.next
		else:
			tail.next = headB
			headB = headB.next
		tail = tail.next
	return dummyNode.next


def sortedMerge(head1, head2):
	dummy = Node(0)
	curr = dummy
	while head1 and head2:
		if head1.data <= head2.data:
			curr.next = head1
			head1 = head1.next
		else:
			curr.next = head2
			head2 = head2.next
		curr = curr.next
	while head1:
		curr.next = head1
		head1 = head1.next
		curr = curr.next
	while head2:
		curr.next = head2
		head2 = head2.next
		curr = curr.next
	return dummy.next


def sortedMerge(head1, head2):
	finalnode = Node(0)
	dongu = True
	if head1.data < head2.data:
		finalnode = head1
		head1 = head1.next
	else:
		finalnode = head2
		head2 = head2.next
	firsthead = finalnode
	while head1 != None and head2 != None:
		if head1.data < head2.data:
			finalnode.next = head1
			head1 = head1.next
			finalnode = finalnode.next
		else:
			finalnode.next = head2
			head2 = head2.next
			finalnode = finalnode.next
	if head1 == None:
		finalnode.next = head2
	if head2 == None:
		finalnode.next = head1
	return firsthead


def sortedMerge(head1, head2):
	z = Node(0)
	e = z
	while True:
		if head1 is None:
			e.next = head2
			break
		if head2 is None:
			e.next = head1
			break
		if head1.data <= head2.data:
			e.next = head1
			head1 = head1.next
		else:
			e.next = head2
			head2 = head2.next
		e = e.next
	return z.next


def sortedMerge(head1, head2):
	dummy = Node(0)
	ml = dummy
	while True:
		if head1 is None:
			ml.next = head2
			break
		if head2 is None:
			ml.next = head1
			break
		if head1.data >= head2.data:
			ml.next = head2
			head2 = head2.next
		else:
			ml.next = head1
			head1 = head1.next
		ml = ml.next
	return dummy.next


def sortedMerge(head1, head2):
	dummy = Node(None)
	curr = dummy
	(p1, p2) = (head1, head2)
	while p1 and p2:
		if p1.data <= p2.data:
			curr.next = p1
			p1 = p1.next
		else:
			curr.next = p2
			p2 = p2.next
		curr = curr.next
	if p1:
		curr.next = p1
	if p2:
		curr.next = p2
	return dummy.next


def sortedMerge(head1, head2):
	dummyNode = Node(0)
	tail = dummyNode
	while True:
		if head1 is None:
			tail.next = head2
			break
		if head2 is None:
			tail.next = head1
			break
		if head1.data <= head2.data:
			tail.next = head1
			head1 = head1.next
		else:
			tail.next = head2
			head2 = head2.next
		tail = tail.next
	return dummyNode.next


def sortedMerge(head1, head2):
	if head1 == None:
		return head2
	if head2 == None:
		return head1
	newnode = Node(0)
	temp = newnode
	while head1 and head2:
		if head1.data <= head2.data:
			temp.next = head1
			head1 = head1.next
			temp = temp.next
		else:
			temp.next = head2
			head2 = head2.next
			temp = temp.next
	if head1:
		temp.next = head1
	if head2:
		temp.next = head2
	return newnode.next


def sortedMerge(head1, head2):
	l1 = []
	while head1:
		l1.append(head1.data)
		head1 = head1.next
	while head2:
		l1.append(head2.data)
		head2 = head2.next
	l1.sort()
	current = Node(l1[0])
	start = current
	for i in range(1, len(l1)):
		k = Node(l1[i])
		current.next = k
		current = k
	return start


def sortedMerge(head1, head2):
	if head1 is None and head2 is None:
		return None
	if head1 is None and head2 is not None:
		return head2
	if head2 is None and head1 is not None:
		return head1
	head = Node(0)
	curr = head
	while head1 and head2:
		if head1.data == head2.data or head1.data < head2.data:
			curr.next = head1
			head1 = head1.next
			curr = curr.next
			curr.next = None
		elif head2.data < head1.data:
			curr.next = head2
			head2 = head2.next
			curr = curr.next
			curr.next = None
	if head1:
		curr.next = head1
	if head2:
		curr.next = head2
	return head.next


def sortedMerge(head1, head2):
	dummy = Node(0)
	current = dummy
	while True:
		if head1 is None:
			current.next = head2
			break
		if head2 is None:
			current.next = head1
			break
		if head1 and head2:
			if head1.data <= head2.data:
				current.next = head1
				head1 = head1.next
			elif head2.data <= head1.data:
				current.next = head2
				head2 = head2.next
		current = current.next
	return dummy.next


def sortedMerge(head1, head2):
	if head1 is None:
		return head2
	elif head2 is None:
		return head1
	temp1 = head1
	temp2 = head2
	if temp1.data < temp2.data:
		head = head1
		prev = temp1
		temp1 = temp1.next
	else:
		head = head2
		prev = temp2
		temp2 = temp2.next
	while temp1 and temp2:
		if temp1.data < temp2.data:
			prev.next = temp1
			prev = temp1
			temp1 = temp1.next
		else:
			prev.next = temp2
			prev = temp2
			temp2 = temp2.next
	if temp2:
		prev.next = temp2
	else:
		prev.next = temp1
	return head


def sortedMerge(head1, head2):
	ans = []
	res = []
	cur = head1
	prev = head2
	while cur:
		ans.append(cur.data)
		cur = cur.next
	while prev:
		res.append(prev.data)
		prev = prev.next
	ans.extend(res)
	ans.sort()
	l = Node(0)
	p = l
	for i in ans:
		k = Node(i)
		l.next = k
		l = l.next
	return p.next


def sortedMerge(head1, head2):
	x = []
	y = []
	temp1 = head1
	temp2 = head2
	while head1 != None:
		x.append(head1.data)
		head1 = head1.next
	while head2 != None:
		y.append(head2.data)
		head2 = head2.next
	z = x + y
	z.sort()
	for i in z:
		print(i, end=' ')


def sortedMerge(head1, head2):
	if head1 == None:
		return head2
	if head2 == None:
		return head1
	temp1 = head1
	temp2 = head2
	ans = None
	while temp1 != None and temp2 != None:
		if temp1.data <= temp2.data:
			temp = temp1
			temp1 = temp1.next
		else:
			temp = temp2
			temp2 = temp2.next
		if ans == None:
			ans = temp
			cur = temp
		else:
			cur.next = temp
			cur = cur.next
	if temp1 != None:
		cur.next = temp1
	if temp2 != None:
		cur.next = temp2
	return ans


def sortedMerge(start1, start2):
	temp1 = temp2 = None
	if start1.data < start2.data:
		temp1 = start1
		temp2 = start2
	else:
		temp1 = start2
		temp2 = start1
	start = temp1
	prev = None
	node = None
	while temp1 and temp2:
		if temp1.data > temp2.data:
			node = temp2
			temp2 = temp2.next
			prev.next = node
			node.next = temp1
			prev = node
		else:
			prev = temp1
			temp1 = temp1.next
	if temp2:
		prev.next = temp2
	return start


def sortedMerge(start1, start2):
	if start1.data < start2.data:
		new = start1
		temp1 = start1
		temp2 = start2
	else:
		new = start2
		temp1 = start2
		temp2 = start1
	while temp1.next and temp2:
		if temp1.data <= temp2.data and temp2.data <= temp1.next.data:
			node = Node(temp2.data)
			node.next = temp1.next
			temp1.next = node
			temp1 = temp1.next
			temp2 = temp2.next
		else:
			temp1 = temp1.next
	if temp2:
		temp1.next = temp2
	return new


def sortedMerge(head1, head2):
	temp1 = head1
	temp2 = head2
	l1 = []
	l2 = []
	while temp1 != None:
		l1.append(temp1.data)
		temp1 = temp1.next
	while temp2 != None:
		l2.append(temp2.data)
		temp2 = temp2.next
	l1 = l1 + l2
	l1 = sorted(l1)
	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


def sortedMerge(left, right):
	if not left:
		return right
	if not right:
		return left
	ans = Node(-1)
	temp = ans
	while left and right:
		if left.data < right.data:
			temp.next = left
			temp = left
			left = left.next
		else:
			temp.next = right
			temp = right
			right = right.next
	if left:
		temp.next = left
	if right:
		temp.next = right
	return ans.next


def sortedMerge(head1, head2):
	temp1 = head1
	temp2 = head2
	sortedList = Node(-1)
	if temp1.data <= temp2.data:
		sortedList.data = temp1.data
		temp1 = temp1.next
	else:
		sortedList.data = temp2.data
		temp2 = temp2.next
	sortedList.next = None
	resHead = sortedList
	while temp1 != None and temp2 != None:
		newNode = Node(-1)
		if temp1.data <= temp2.data:
			sortedList.next = newNode
			newNode.data = temp1.data
			temp1 = temp1.next
		else:
			sortedList.next = newNode
			newNode.data = temp2.data
			temp2 = temp2.next
		sortedList = sortedList.next
	while temp1 != None:
		newNode = Node(-1)
		sortedList.next = newNode
		newNode.data = temp1.data
		temp1 = temp1.next
		sortedList = sortedList.next
	while temp2 != None:
		newNode = Node(-1)
		sortedList.next = newNode
		newNode.data = temp2.data
		temp2 = temp2.next
		sortedList = sortedList.next
	return resHead


def sortedMerge(head1, head2):
	temp1 = head1
	temp2 = head2
	a = []
	b = []
	while temp1:
		a += [temp1.data]
		temp1 = temp1.next
	while temp2:
		b += [temp2.data]
		temp2 = temp2.next
	a.extend(b)
	a.sort()
	head = Node(a[0])
	T = head
	for i in range(1, len(a)):
		x = Node(a[i])
		head.next = x
		head = head.next
	return T


def sortedMerge(h1, h2):
	if h1 == None:
		return h2
	if h2 == None:
		return h1
	if h1.data > h2.data:
		(h1, h2) = (h2, h1)
	res = h1
	while h1 and h2:
		temp = None
		while h1 and h1.data <= h2.data:
			temp = h1
			h1 = h1.next
		temp.next = h2
		(h1, h2) = (h2, h1)
	return res


def sortedMerge(head1, head2):
	if head1 is None:
		return head2
	if head2 is None:
		return head1
	ptr1 = head1
	ptr2 = head2
	dummy = Node(0)
	tail = dummy
	while ptr1 is not None and ptr2 is not None:
		if ptr1.data <= ptr2.data:
			tail.next = ptr1
			ptr1 = ptr1.next
		else:
			tail.next = ptr2
			ptr2 = ptr2.next
		tail = tail.next
	while ptr1 is not None:
		tail.next = ptr1
		ptr1 = ptr1.next
		tail = tail.next
	while ptr2 is not None:
		tail.next = ptr2
		ptr2 = ptr2.next
		tail = tail.next
	return dummy.next


def solve(head1, head2):
	if head1.next == None:
		head1.next = head2
		return head1
	res = Node(-1)
	dummy = res
	while head1 and head2:
		if head1.data < head2.data:
			res.next = head1
			head1 = head1.next
		else:
			res.next = head2
			head2 = head2.next
		res = res.next
	while head1:
		res.next = head1
		head1 = head1.next
		res = res.next
	while head2:
		res.next = head2
		head2 = head2.next
		res = res.next
	return dummy.next

def sortedMerge(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 sortedMerge(head1, head2):
	L1 = []
	n = head1
	while n is not None:
		L1.append(n.data)
		n = n.next
	L2 = []
	n = head2
	while n is not None:
		L2.append(n.data)
		n = n.next
	L = L1 + L2
	L.sort()
	head1.next = None
	n = head1
	while L:
		a = L.pop(0)

		def add(a):
			new_node = Node(a)
			n.next = new_node
		add(a)
		n = n.next
	return head1.next


def solve(temp1, temp2):
	while temp2 is not None and temp1.next is not None:
		curr = temp1.next
		if temp2.data >= temp1.data and temp2.data <= curr.data:
			temp1.next = temp2
			temp2 = temp2.next
			temp1.next.next = curr
			temp1 = temp1.next
		else:
			temp1 = curr
			curr = curr.next
	if temp2 is not None:
		temp1.next = temp2

def sortedMerge(head1, head2):
	if head1 is None:
		return head2
	if head2 is None:
		return head1
	val1 = head1.data
	val2 = head2.data
	temp1 = head1
	temp2 = head2
	if val1 <= val2:
		solve(temp1, temp2)
		return head1
	else:
		solve(temp2, temp1)
		return head2


def solve(temp, temp1, temp2):
	while temp1 is not None and temp2 is not None:
		if temp1.data <= temp2.data:
			newNode = Node(temp1.data)
			temp.next = newNode
			temp = temp.next
			temp1 = temp1.next
		else:
			newNode = Node(temp2.data)
			temp.next = newNode
			temp = temp.next
			temp2 = temp2.next
	while temp1 is not None:
		newNode = Node(temp1.data)
		temp.next = newNode
		temp = temp.next
		temp1 = temp1.next
	while temp2 is not None:
		newNode = Node(temp2.data)
		temp.next = newNode
		temp = temp.next
		temp2 = temp2.next

def sortedMerge(head1, head2):
	if head1 is None:
		return head2
	if head2 is None:
		return head1
	val1 = head1.data
	val2 = head2.data
	temp = Node(-1)
	head = temp
	temp1 = head1
	temp2 = head2
	if val1 <= val2:
		temp.data = val1
		temp1 = temp1.next
		solve(temp, temp1, temp2)
	else:
		temp.data = val2
		temp2 = temp2.next
		solve(temp, temp1, temp2)
	return head


def sortedMerge(head1, head2):
	z = Node(-1)
	start = z
	while head1 and head2:
		if head1.data <= head2.data:
			start.next = head1
			head1 = head1.next
			start = start.next
		else:
			start.next = head2
			head2 = head2.next
			start = start.next
	while head1:
		start.next = head1
		head1 = head1.next
		start = start.next
	while head2:
		start.next = head2
		head2 = head2.next
		start = start.next
	return z.next


def sortedMerge(head1, head2):
	if not head1:
		return head2
	if not head2:
		return head1
	newnew = Node(0)
	currr = newnew
	cur = head1
	cur2 = head2
	while cur and cur2:
		if cur.data <= cur2.data:
			currr.next = cur
			cur = cur.next
		else:
			currr.next = cur2
			cur2 = cur2.next
		currr = currr.next
	if cur:
		currr.next = cur
		cur = cur.next
	if cur2:
		currr.next = cur2
		cur2 = cur2.next
	return newnew.next


def sortedMerge(head1, head2):
	if head1 is None:
		return head2
	if head2 is None:
		return head1
	if head1.data > head2.data:
		(head1, head2) = (head2, head1)
	res = head1
	while head1 and head2:
		tmp = None
		while head1 and head1.data <= head2.data:
			tmp = head1
			head1 = head1.next
		tmp.next = head2
		(head1, head2) = (head2, head1)
	return res


def sortedMerge(head1, head2):
	head = None
	tail = None
	curr1 = head1
	curr2 = head2
	while curr1 != None and curr2 != None:
		if curr1.data <= curr2.data:
			if head == None:
				head = curr1
				tail = curr1
				curr1 = curr1.next
			else:
				tail.next = curr1
				curr1 = curr1.next
				tail = tail.next
				tail.next = None
		elif head == None:
			head = curr2
			tail = curr2
			curr2 = curr2.next
		else:
			tail.next = curr2
			curr2 = curr2.next
			tail = tail.next
			tail.next = None
	while curr1 != None:
		tail.next = curr1
		curr1 = curr1.next
		tail = tail.next
		tail.next = None
	while curr2 != None:
		tail.next = curr2
		curr2 = curr2.next
		tail = tail.next
		tail.next = None
	return head


def sortedMerge(head1, head2):
	new = a = Node(0)
	while head1 and head2:
		if head1.data <= head2.data:
			a.next = head1
			a = a.next
			head1 = head1.next
		else:
			a.next = head2
			a = a.next
			head2 = head2.next
	while head1:
		a.next = head1
		head1 = head1.next
		a = a.next
	while head2:
		a.next = head2
		head2 = head2.next
		a = a.next
	a.next = None
	return new.next


def sortedMerge(head1, head2):
	head = Node(0)
	curr = head
	while head1 and head2:
		if head1.data < head2.data:
			curr.next = head1
			head1 = head1.next
		else:
			curr.next = head2
			head2 = head2.next
		curr = curr.next
	if head1 != None:
		curr.next = head1
	else:
		curr.next = head2
	return head.next


def sortedMerge(head1, head2):
	if head1 == None:
		return head2
	if head2 == None:
		return head1
	if head1.data > head2.data:
		temp = head2.next
		head2.next = head1
		head1 = head2
		head2 = temp
	temp = head1
	prev = temp
	while temp != None and head2 != None:
		if temp.data > head2.data:
			prev.next = head2
			temp2 = head2.next
			head2.next = temp
			prev = prev.next
			head2 = temp2
		else:
			prev = temp
			temp = temp.next
	while head2 != None:
		prev.next = head2
		head2 = head2.next
		prev = prev.next
	return head1


def sortedMerge(head1, head2):
	temp = Node(-1)
	curr = temp
	while head1 and head2:
		if head1.data <= head2.data:
			curr.next = Node(head1.data)
			head1 = head1.next
			curr = curr.next
		else:
			curr.next = Node(head2.data)
			curr = curr.next
			head2 = head2.next
	while head1:
		curr.next = Node(head1.data)
		head1 = head1.next
		curr = curr.next
	while head2:
		curr.next = Node(head2.data)
		curr = curr.next
		head2 = head2.next
	return temp.next


def sortedMerge(head1, head2):
	if head1 is None:
		return head2
	if head2 is None:
		return head1
	dummy = Node(None)
	tail = dummy
	while head1 and head2:
		if head1.data < head2.data:
			tail.next = head1
			head1 = head1.next
		else:
			tail.next = head2
			head2 = head2.next
		tail = tail.next
	if head1:
		tail.next = head1
	else:
		tail.next = head2
	return dummy.next

def sortedMerge(head1, head2):
	if head1 is None:
		return head2
	if head2 is None:
		return head1
	if head1.data > head2.data:
		(head1, head2) = (head2, head1)
	res = head1
	while head1 and head2:
		temp = None
		while head1 and head1.data <= head2.data:
			temp = head1
			head1 = head1.next
		temp.next = head2
		(head1, head2) = (head2, head1)
	return res


def sortedMerge(list1, list2):
	ans = Node(123)
	a = ans
	cur1 = list1
	cur2 = list2
	while cur1 and cur2:
		if cur1.data < cur2.data:
			a.next = cur1
			cur1 = cur1.next
		else:
			a.next = cur2
			cur2 = cur2.next
		a = a.next
	while cur1:
		a.next = cur1
		cur1 = cur1.next
		a = a.next
	while cur2:
		a.next = cur2
		cur2 = cur2.next
		a = a.next
	return ans.next


class Node:

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

class LinkedList:

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

	def append(self, new_value):
		new_node = Node(new_value)
		if self.head == None:
			self.head = new_node
			self.tail = new_node
		else:
			self.tail.next = new_node
			self.tail = new_node

def sortedMerge(head1, head2):
	final = LinkedList()
	while head1 and head2:
		if head1.data < head2.data:
			final.append(head1.data)
			head1 = head1.next
		else:
			final.append(head2.data)
			head2 = head2.next
	while head1:
		final.tail.next = head1
		final.tail = final.tail.next
		head1 = head1.next
	while head2:
		final.tail.next = head2
		final.tail = final.tail.next
		head2 = head2.next
	return final.head


def sortedMerge(head1, head2):
	l = []
	l1 = []
	l2 = []
	t = head1
	while t:
		l.append(t.data)
		t = t.next
	t = head2
	while t:
		l1.append(t.data)
		t = t.next
	l2 = l1 + l
	l2.sort()
	for i in l2:
		print(i, end=' ')


def sortedMerge(head1, head2):
	a = head1
	(p, q) = ([], [])
	while a is not None:
		p.append(a.data)
		a = a.next
	b = head2
	while b is not None:
		q.append(b.data)
		b = b.next
	list1 = sorted(p + q)
	c = None
	head3 = None
	for i in list1:
		m = Node(i)
		if head3 is None:
			head3 = m
			c = head3
		else:
			c.next = m
			c = c.next
	return head3


def sortedMerge(h1, h2):
	ans = Node(-1)
	head_ans = ans
	while h1 or h2:
		if h1 != None and h2 != None:
			if h1.data < h2.data:
				tmp = Node(h1.data)
				ans.next = tmp
				ans = ans.next
				h1 = h1.next
			else:
				tmp = Node(h2.data)
				ans.next = tmp
				ans = ans.next
				h2 = h2.next
		elif h1 == None:
			ans.next = h2
			break
		elif h2 == None:
			ans.next = h1
			break
	return head_ans.next


def sortedMerge(head1, head2):
	dummy = Node(-1)
	res = dummy
	(curr1, curr2) = (head1, head2)
	while curr1 and curr2:
		if curr1.data > curr2.data:
			res.next = curr2
			curr2 = curr2.next
		else:
			res.next = curr1
			curr1 = curr1.next
		res = res.next
	if curr1:
		res.next = curr1
	else:
		res.next = curr2
	return dummy.next


def sortedMerge(head1, head2):
	NewList = LinkedList()
	node1 = head1
	node2 = head2
	while node1 != None and node2 != None:
		if node1.data <= node2.data:
			NewList.append(node1.data)
			node1 = node1.next
		else:
			NewList.append(node2.data)
			node2 = node2.next
	while node1 != None:
		NewList.append(node1.data)
		node1 = node1.next
	while node2 != None:
		NewList.append(node2.data)
		node2 = node2.next
	return NewList.head


class Node:

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

def sortedMerge(head1, head2):
	r = Node(0)
	head = r
	p = head1
	q = head2
	while p and q:
		if p.data < q.data:
			r.next = p
			p = p.next
		else:
			r.next = q
			q = q.next
		r = r.next
	while p:
		r.next = p
		p = p.next
		r = r.next
	while q:
		r.next = q
		q = q.next
		r = r.next
	return head.next


def sortedMerge(head1, head2):
	if head1.data < head2.data:
		r = head1
		c = head1
		head1 = head1.next
	else:
		r = head2
		c = head2
		head2 = head2.next
	while True:
		if head1 == None:
			c.next = head2
			return r
		elif head2 == None:
			c.next = head1
			return r
		if head1.data < head2.data:
			c.next = head1
			head1 = head1.next
			c = c.next
		else:
			c.next = head2
			head2 = head2.next
			c = c.next


def mergeUtil(h1, h2):
	if h1.next == None:
		h1.next = h2
		return h1
	curr1 = h1
	next1 = h1.next
	curr2 = h2
	next2 = h2.next
	while next1 != None and curr2 != None:
		if curr2.data <= next1.data and curr2.data >= curr1.data:
			next2 = curr2.next
			curr1.next = curr2
			curr2.next = next1
			curr1 = curr2
			next1 = curr1.next
			curr2 = next2
		elif next1.next != None:
			curr1 = next1
			next1 = curr1.next
		else:
			next1.next = curr2
			return h1
	return h1

def sortedMerge(head1, head2):
	if head1 is None:
		return head2
	if head2 is None:
		return head1
	if head1.data <= head2.data:
		return mergeUtil(head1, head2)
	else:
		return mergeUtil(head2, head1)


def sortedMerge(head1, head2):
	dummy = Node(-1)
	result = dummy
	while head1 and head2:
		if head1.data <= head2.data:
			dummy.next = head1
			head1 = head1.next
		else:
			dummy.next = head2
			head2 = head2.next
		dummy = dummy.next
	if head1:
		dummy.next = head1
	if head2:
		dummy.next = head2
	return result.next


def sortedMerge(head1, head2):
	newhead = None
	temp = newhead
	while head1 and head2:
		if head1.data > head2.data:
			if newhead == None:
				newhead = head2
				temp = newhead
			else:
				temp.next = head2
				temp = temp.next
			head2 = head2.next
		else:
			if newhead == None:
				newhead = head1
				temp = newhead
			else:
				temp.next = head1
				temp = temp.next
			head1 = head1.next
	while head1:
		if newhead == None:
			newhead = head1
			temp = newhead
		else:
			temp.next = head1
			temp = temp.next
		head1 = head1.next
	while head2:
		if newhead == None:
			newhead = head2
			temp = newhead
		else:
			temp.next = head2
			temp = temp.next
		head2 = head2.next
	return newhead


def sortedMerge(head1, head2):
	d1 = head1
	d2 = head2
	if d1.data > d2.data:
		(d1, d2) = (d2, d1)
	ans = d1
	while d1 and d2:
		temp = Node(0)
		while d1 and d1.data <= d2.data:
			temp = d1
			d1 = d1.next
		temp.next = d2
		(d1, d2) = (d2, d1)
	return ans


class Node:

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

def sortedMerge(head1, head2):
	dummyNode = Node(-1)
	auxA = head1
	auxB = head2
	tail = dummyNode
	breakLoop = False
	while not breakLoop:
		if auxA == None:
			tail.next = auxB
			breakLoop = True
		elif auxB == None:
			tail.next = auxA
			breakLoop = True
		elif auxA.data <= auxB.data:
			tail.next = auxA
			auxA = auxA.next
		else:
			tail.next = auxB
			auxB = auxB.next
		tail = tail.next
	return dummyNode.next


def sortedMerge(head1, head2):
	dummy = Node
	cur = dummy
	while True:
		if head1.data <= head2.data:
			cur.next = head1
			head1 = head1.next
		else:
			cur.next = head2
			head2 = head2.next
		cur = cur.next
		if head1 is None and head2:
			cur.next = head2
			break
		if head2 is None and head1:
			cur.next = head1
			break
	return dummy.next


def sortedMerge(head1, head2):
	l = []
	while head1 != None:
		l.append(head1.data)
		head1 = head1.next
	while head2 != None:
		l.append(head2.data)
		head2 = head2.next
	l.sort()
	head = Node(l[0])
	x = head
	for i in range(1, len(l)):
		y = Node(l[i])
		x.next = y
		x = y
	return head


def sortedMerge(head1, head2):
	tmp = temp = None
	while head1 and head2:
		if head1.data <= head2.data:
			if not tmp:
				temp = head1
				tmp = head1
			else:
				tmp.next = head1
				tmp = tmp.next
			head1 = head1.next
		else:
			if not tmp:
				temp = head2
				tmp = head2
			else:
				tmp.next = head2
				tmp = tmp.next
			head2 = head2.next
	while head1:
		tmp.next = head1
		tmp = tmp.next
		head1 = head1.next
	while head2:
		tmp.next = head2
		tmp = tmp.next
		head2 = head2.next
	return temp


def sortedMerge(head1, head2):
	a = head1
	b = head2
	u = []
	v = []
	while a:
		u.append(a.data)
		a = a.next
	while b:
		v.append(b.data)
		b = b.next
	u = u + v
	u = sorted(u)
	head = Node(u[0])
	t = head
	for i in range(1, len(u)):
		x = Node(u[i])
		head.next = x
		head = head.next
	return t


def sortedMerge(h1, h2):
	if h1.data > h2.data:
		(h1, h2) = (h2, h1)
	res = h1
	while h1 and h2:
		temp = Node(0)
		while h1 and h1.data <= h2.data:
			temp = h1
			h1 = h1.next
		temp.next = h2
		(h1, h2) = (h2, h1)
	return res


def sortedMerge(head1, head2):
	dummy_node = Node(0)
	prev = dummy_node
	(curr1, curr2) = (head1, head2)
	while True:
		if curr1 is None:
			prev.next = curr2
			break
		if curr2 is None:
			prev.next = curr1
			break
		if curr1.data <= curr2.data:
			prev.next = curr1
			curr1 = curr1.next
			prev = prev.next
		else:
			prev.next = curr2
			curr2 = curr2.next
			prev = prev.next
	return dummy_node.next


def sortedMerge(head1, head2):
	a = []
	b = []
	h1 = head1
	h2 = head2
	while h1:
		a.append(h1.data)
		h1 = h1.next
	while h2:
		b.append(h2.data)
		h2 = h2.next
	r = a + b
	r.sort()
	head = None
	for i in range(len(r) - 1, -1, -1):
		ne = Node(r[i])
		ne.next = head
		head = ne
	return head


def sortedMerge(head1, head2):
	temp1 = head1
	temp2 = head2
	result = []
	while temp1.next is not None:
		result.append(temp1.data)
		temp1 = temp1.next
	result.append(temp1.data)
	temp1.next = head2
	while temp2 is not None:
		result.append(temp2.data)
		temp2 = temp2.next
	result.sort()
	temp1 = head1
	i = 0
	while temp1 is not None:
		temp1.data = result[i]
		i += 1
		temp1 = temp1.next
	return head1


def sortedMerge(head1, head2):
	if head1 is None:
		return head2
	if head2 is None:
		return head1
	p1 = head1
	p2 = head2
	dummy = Node(0)
	tail = dummy
	while p1 is not None and p2 is not None:
		if p1.data <= p2.data:
			tail.next = p1
			p1 = p1.next
		else:
			tail.next = p2
			p2 = p2.next
		tail = tail.next
	if p1 is not None:
		tail.next = p1
	if p2 is not None:
		tail.next = p2
	return dummy.next


def sortedMerge(head1, head2):
	if not head1:
		return head2
	if not head2:
		return head1
	dum = Node(0)
	curr = dum
	while head1 and head2:
		if head1.data <= head2.data:
			curr.next = head1
			head1 = head1.next
		else:
			curr.next = head2
			head2 = head2.next
		curr = curr.next
	if head1:
		curr.next = head1
	else:
		curr.next = head2
	return dum.next


def findsmaller(curr, t1):
	if curr.data < t1.data:
		return curr
	return t1

def sortedMerge(head1, head2):
	t1 = head1
	t2 = head2
	if t1.data > t2.data:
		curr = head2
		while t1 != None and curr.next != None:
			temp = curr.next
			curr.next = findsmaller(curr.next, t1)
			if curr.next != t1:
				curr = curr.next
			else:
				curr = t1
				head1 = t1.next
				t1.next = temp
				t1 = head1
		if curr.next == None:
			if curr.data < t1.data:
				curr.next = head1
				return head2
		elif t1 == None:
			return head2
	else:
		curr = head1
		while t2 != None and curr.next != None:
			temp = curr.next
			curr.next = findsmaller(curr.next, t2)
			if curr.next != t2:
				curr = curr.next
			else:
				curr = t2
				head2 = t2.next
				t2.next = temp
				t2 = head2
		if curr.next == None:
			if curr.data < t2.data:
				curr.next = head2
				return head1
		elif t2 == None:
			return head1


def sortedMerge(head1, head2):
	if not head1:
		return head2
	if not head2:
		return head1
	if head1.data < head2.data:
		newH = head1
		head1 = head1.next
		newT = newH
	else:
		newH = head2
		head2 = head2.next
		newT = newH
	while head1 and head2:
		if head1.data < head2.data:
			newT.next = head1
			newT = newT.next
			head1 = head1.next
		else:
			newT.next = head2
			head2 = head2.next
			newT = newT.next
	while head1:
		newT.next = head1
		newT = newT.next
		head1 = head1.next
	while head2:
		newT.next = head2
		head2 = head2.next
		newT = newT.next
	return newH


def sortedMerge(head1, head2):
	newLL = Node(0)
	c1 = head1
	c2 = head2
	tempTail = newLL
	while c1 != None and c2 != None:
		if c1.data >= c2.data:
			tempTail.next = c2
			c2 = c2.next
		else:
			tempTail.next = c1
			c1 = c1.next
		tempTail = tempTail.next
	if c1 != None:
		tempTail.next = c1
	else:
		tempTail.next = c2
	return newLL.next


def sortedMerge(head1, head2):
	(curr1, curr2) = (head1, head2)
	if curr2.data < curr1.data:
		merged_head = curr2
		curr2 = curr2.next
	else:
		merged_head = curr1
		curr1 = curr1.next
	merged_tail = merged_head
	while curr1 != None and curr2 != None:
		node = Node(10000000)
		if curr2.data <= curr1.data:
			node = curr2
			curr2 = curr2.next
		else:
			node = curr1
			curr1 = curr1.next
		merged_tail.next = node
		merged_tail = node
	if curr1 == None:
		merged_tail.next = curr2
	else:
		merged_tail.next = curr1
	return merged_head


def sortedMerge(head1, head2):
	a = head1
	b = head2
	u = []
	v = []
	while a != None:
		u.append(a.data)
		a = a.next
	while b != None:
		v.append(b.data)
		b = b.next
	u = u + v
	u.sort()
	head = Node(u[0])
	t = head
	for j in range(1, len(u)):
		x = Node(u[j])
		head.next = x
		head = head.next
	return t


def sortedMerge(head1, head2):
	l1 = head1
	l2 = head2
	if l1.data > l2.data:
		(l1, l2) = (l2, l1)
	res = l1
	while l1 and l2:
		temp = Node(-1)
		temp = None
		while l1 and l1.data <= l2.data:
			temp = l1
			l1 = l1.next
		temp.next = l2
		(l1, l2) = (l2, l1)
	return res


def sortedMerge(head1, head2):
	dummy = Node(-1)
	tail = dummy
	curr1 = head1
	curr2 = head2
	while curr1 != None and curr2 != None:
		if curr1.data < curr2.data:
			tail.next = curr1
			curr1 = curr1.next
		else:
			tail.next = curr2
			curr2 = curr2.next
		tail = tail.next
	if curr1 == None:
		tail.next = curr2
	elif curr2 == None:
		tail.next = curr1
	return dummy.next