Given two linked lists, your task is to complete the function makeUnion(), that returns the union list of two linked lists. This union list should include all the distinct elements only and it should be sorted in ascending order.
Example 1:
Input:
L1 = 9->6->4->2->3->8
L2 = 1->2->8->6->2
Output: 
1 2 3 4 6 8 9
Explaination: 
All the distinct numbers from two lists, when sorted forms the list in the output. 
Example 2:
Input:
L1 = 1->5->1->2->2->5
L2 = 4->5->6->7->1
Output: 
1 2 4 5 6 7
Explaination: 
All the distinct numbers from two lists, when sorted forms the list in the output.
Your Task:
The task is to complete the function makeUnion() which makes the union of the given two lists and returns the head of the new list.
Expected Time Complexity: O((N+M)*Log(N+M))
Expected Auxiliary Space: O(N+M)
Constraints:
1<=N,M<=10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Sorting

Data structures

Starter code: #User function Template for python3

class Solution:
    def union(self, head1,head2):
        # code here
        # return head of resultant linkedlist



Solutions:
def union(head1, head2):
	a = []
	b = []
	while head1 != None:
		a.append(head1.data)
		head1 = head1.next
	while head2 != None:
		b.append(head2.data)
		head2 = head2.next
	c = a + b
	d = list(set(c))
	d.sort()
	for i in d:
		print(i, end=' ')


def union(head1, head2):
	s = set()
	while head1 != None:
		s.add(head1.data)
		head1 = head1.next
	while head2 != None:
		s.add(head2.data)
		head2 = head2.next
	a = []
	for i in s:
		a.append(i)
	a.sort()
	for i in a:
		print(i, end=' ')


def union(head1, head2):
	curr = head1
	a = []
	while curr:
		a.append(curr.data)
		curr = curr.next
	curr = head2
	while curr:
		a.append(curr.data)
		curr = curr.next
	a = list(set(a))
	x = []
	for i in a:
		x.append(i)
	x.sort()
	for i in x:
		print(i, end=' ')


def union(head1, head2):
	d = {}
	while head1 != None:
		if head1.data not in d:
			d[head1.data] = head1.data
		head1 = head1.next
	while head2 != None:
		if head2.data not in d:
			d[head2.data] = head2.data
		head2 = head2.next
	head = linkedList()
	for (key, val) in sorted(d.items()):
		head.insert(key)
	return head.head


def union(head1, head2):
	s1 = set()
	s2 = set()
	cur = head1
	prev = head2
	while cur:
		s1.add(cur.data)
		cur = cur.next
	while prev:
		s2.add(prev.data)
		prev = prev.next
	res = sorted(s1.union(s2))
	n = Node(0)
	h = n
	for i in res:
		k = Node(i)
		n.next = k
		n = n.next
	return h.next


def union(head1, head2):
	temp1 = head1
	temp2 = head2
	a = []
	while temp1:
		a.append(temp1.data)
		temp1 = temp1.next
	while temp2:
		a.append(temp2.data)
		temp2 = temp2.next
	a = list(set(a))
	a.sort()
	for i in a:
		print(i, end=' ')


def union(head1, head2):
	s = set()
	curr_node = head1
	while curr_node:
		s.add(curr_node.data)
		curr_node = curr_node.next
	curr_node = head2
	while curr_node:
		s.add(curr_node.data)
		curr_node = curr_node.next
	lst3 = list(s)
	lst3.sort()
	L1 = linkedList()
	curr_node = L1.head
	for item in lst3:
		new_node = Node(item)
		if curr_node:
			curr_node.next = new_node
			curr_node = curr_node.next
		else:
			L1.head = new_node
			curr_node = L1.head
	return L1.head


def union(head1, head2):
	lst1 = []
	lst2 = []
	curr_node = head1
	while curr_node:
		lst1.append(curr_node.data)
		curr_node = curr_node.next
	curr_node = head2
	while curr_node:
		lst2.append(curr_node.data)
		curr_node = curr_node.next
	lst3 = list(set(lst1 + lst2))
	lst3.sort()
	L1 = linkedList()
	curr_node = L1.head
	for item in lst3:
		new_node = Node(item)
		if curr_node:
			curr_node.next = new_node
			curr_node = curr_node.next
		else:
			L1.head = new_node
			curr_node = L1.head
	return L1.head


def union(head1, head2):
	i = []
	while head1 or head2:
		if head1:
			i.append(head1.data)
			head1 = head1.next
		if head2:
			i.append(head2.data)
			head2 = head2.next
	i = sorted(list(set(i)))
	for a in i:
		print(a, end=' ')


def union(head1, head2):
	n1 = head1
	s1 = set()
	while n1 is not None:
		s1.add(n1.data)
		n1 = n1.next
	n2 = head2
	s2 = set()
	while n2 is not None:
		s2.add(n2.data)
		n2 = n2.next
	a = list(s1 | s2)
	a.sort()
	new = Node(0)
	n = new
	while a:
		new_node = Node(a.pop(0))
		n.next = new_node
		n = n.next
	return new.next


def union(head1, head2):
	h1 = []
	t1 = head1
	while t1:
		h1.append(t1.data)
		t1 = t1.next
	h2 = []
	t2 = head2
	while t2:
		h2.append(t2.data)
		t2 = t2.next
	res = sorted(list(set(h1 + h2)))
	llr = linkedList()
	for x in res:
		llr.insert(x)
	return llr.head


def union(head1, head2):
	ans = list()
	while head1 or head2:
		if head1 == None:
			ans.append(head2.data)
			head2 = head2.next
		elif head2 == None:
			ans.append(head1.data)
			head1 = head1.next
		else:
			ans.append(head1.data)
			ans.append(head2.data)
			(head1, head2) = (head1.next, head2.next)
	ans.sort()
	node = Node(-1)
	head = node
	for x in range(len(ans)):
		if node.data == ans[x]:
			continue
		temp = Node(ans[x])
		node.next = temp
		node = node.next
	return head.next


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


def union(head1, head2):
	l = []
	ll = []
	n = head1
	nn = head2
	while n:
		l.append(n.data)
		n = n.next
	while nn:
		ll.append(nn.data)
		nn = nn.next
	l += ll
	s = set(l)
	ss = list(s)
	ss.sort()
	ls = linkedList()
	for i in ss:
		ls.insert(i)
	return ls.head


def union(head1, head2):
	p = head1
	s = []
	while p:
		s.append(p.data)
		p = p.next
	p = head2
	while p:
		s.append(p.data)
		p = p.next
	x = list(set(s))
	x.sort()
	ll = linkedList()
	for i in x:
		ll.insert(i)
	return ll.head


def union(head1, head2):
	li = []
	temp = head1
	while temp:
		li.append(temp.data)
		temp = temp.next
	temp1 = head2
	while temp1:
		li.append(temp1.data)
		temp1 = temp1.next
	li = list(set(li))
	li.sort()
	p = Node(0)
	temp = p
	while li:
		temp.next = Node(li.pop(0))
		temp = temp.next
	return p.next


def union(head1, head2):
	s = set()
	while head1:
		s.add(head1.data)
		head1 = head1.next
	while head2:
		s.add(head2.data)
		head2 = head2.next
	l = list(s)
	l.sort()
	res = linkedList()
	for x in l:
		res.insert(x)
	return res.head


def union(head1, head2):
	rec = set()
	while head1:
		rec.add(head1.data)
		head1 = head1.next
	while head2:
		rec.add(head2.data)
		head2 = head2.next
	lst = list(rec)
	lst.sort()
	res = linkedList()
	for x in lst:
		res.insert(x)
	return res.head


def union(head1, head2):
	d = {}
	while head1.next != None:
		d[head1.data] = 1
		head1 = head1.next
	d[head1.data] = 1
	while head2.next != None:
		d[head2.data] = 1
		head2 = head2.next
	d[head2.data] = 1
	l = list(d.keys())
	l.sort()
	w = 0
	a = []
	for j in l:
		if w == 0:
			p = Node(j)
			a.append(p)
			w += 1
		else:
			p.next = Node(j)
			p = p.next
	return a[0]


def union(head1, head2):
	temp = head1
	lst = []
	cnt = 0
	d = {}
	while temp:
		if temp.data in d:
			d[temp.data] += 1
		else:
			d[temp.data] = 1
		temp = temp.next
	temp = head2
	while temp:
		if temp.data in d:
			d[temp.data] += 1
		else:
			d[temp.data] = 1
		temp = temp.next
	for i in d.keys():
		lst.append(i)
	lst.sort()
	for i in lst:
		print(i, end=' ')


def union(head1, head2):
	temp = head1
	sett = set()
	lst = []
	while temp:
		lst.append(temp.data)
		temp = temp.next
	temp = head2
	while temp:
		lst.append(temp.data)
		temp = temp.next
	lst = list(set(lst))
	lst.sort()
	for i in lst:
		print(i, end=' ')


def union(head1, head2):
	list = []
	head = linkedList()
	while head1 != None or head2 != None:
		if head1 != None or head2 == None:
			list.append(head1.data)
			head1 = head1.next
		elif head1 == None or head2 != None:
			list.append(head2.data)
			head2 = head2.next
	list.sort()
	list.append(90)
	ref = []
	i = 0
	while i < len(list) - 1:
		if list[i] != list[i + 1]:
			ref.append(list[i])
		i += 1
	for i in ref:
		head.insert(i)
	return head.head


def union(head1, head2):
	kmap = set()
	ptr = head1
	while ptr:
		kmap.add(ptr.data)
		ptr = ptr.next
	ptr = head2
	while ptr:
		kmap.add(ptr.data)
		ptr = ptr.next
	arr = list(kmap)
	arr.sort()
	dum = Node(-1)
	ptr = dum
	for ele in arr:
		nn = Node(ele)
		ptr.next = nn
		ptr = ptr.next
	return dum.next


def union(head1, head2):
	current_1 = head1
	current_2 = head2
	temp_list_1 = []
	temp_list_2 = []
	third_linked_list = linkedList()
	while current_1:
		temp_list_1.append(current_1.data)
		current_1 = current_1.next
	while current_2:
		temp_list_2.append(current_2.data)
		current_2 = current_2.next
	temp_list = set(temp_list_1) | set(temp_list_2)
	temp_list = sorted(temp_list)
	for elements in temp_list:
		third_linked_list.insert(elements)
	return third_linked_list.head


def union(head1, head2):
	if head1 == None and head2 == None:
		return None
	if head1 == None:
		return head2
	if head2 == None:
		return head1
	temp1 = head1
	temp2 = head2
	l = []
	while temp1 != None and temp2 != None:
		if temp1.data not in l:
			l.append(temp1.data)
		if temp2.data not in l:
			l.append(temp2.data)
		temp1 = temp1.next
		temp2 = temp2.next
	while temp1 != None:
		if temp1.data not in l:
			l.append(temp1.data)
		temp1 = temp1.next
	while temp2 != None:
		if temp2.data not in l:
			l.append(temp2.data)
		temp2 = temp2.next
	newHead = None
	l.sort()
	for i in l:
		dummy = Node(i)
		if newHead == None:
			newHead = dummy
		else:
			temp = newHead
			while temp.next != None:
				temp = temp.next
			temp.next = dummy
	return newHead


def union(head1, head2):
	newlist = []
	while head1:
		newlist.append(head1.data)
		head1 = head1.next
	while head2:
		newlist.append(head2.data)
		head2 = head2.next
	sortedlist = sorted(list(set(newlist)))
	dummy = Node(0)
	curr = dummy
	for element in sortedlist:
		newNode = Node(element)
		curr.next = newNode
		curr = curr.next
	return dummy.next


def union(head1, head2):
	llist = []
	p1 = head1
	p2 = head2
	s = set()
	while p1:
		s.add(p1.data)
		p1 = p1.next
	while p2:
		if p2.data not in s:
			s.add(p2.data)
		p2 = p2.next
	for e in s:
		llist.append(e)
	llist.sort()
	dummy = Node(0)
	curr = dummy
	for ele in llist:
		newnode = Node(ele)
		curr.next = newnode
		curr = curr.next
	return dummy.next


def union(head1, head2):
	union = set()
	stack1 = [head1]
	stack2 = [head2]
	while len(stack1) > 0:
		current1 = stack1.pop()
		union.add(current1.data)
		if current1.next:
			stack1.append(current1.next)
	while len(stack2) > 0:
		current2 = stack2.pop()
		union.add(current2.data)
		if current2.next:
			stack2.append(current2.next)
	union = sorted(union)
	uList = []
	for item in union:
		uList.append(item)
	head = Node(uList[0])
	lastNode = head
	for i in range(1, len(uList)):
		node = Node(uList[i])
		lastNode.next = node
		lastNode = node
	lastNode.next = None
	return head


def union(head1, head2):
	s = set()
	while head1 or head2:
		if head1:
			if head1 not in s:
				s.add(head1.data)
			head1 = head1.next
		if head2:
			if head2 not in s:
				s.add(head2.data)
			head2 = head2.next
	a = b = Node(0)
	for i in sorted(s):
		a.next = Node(i)
		a = a.next
	return b.next


def union(head1, head2):
	a = []
	while head1:
		a.append(head1.data)
		head1 = head1.next
	while head2:
		a.append(head2.data)
		head2 = head2.next
	s = sorted(list(set(a)))
	d = Node(-1)
	p = d
	i = 0
	while i < len(s):
		d.next = Node(s[i])
		d = d.next
		i = i + 1
	return p.next


def union(head1, head2):
	l = []
	p = head1
	q = head2
	while p != None:
		if p.data not in l:
			l.append(p.data)
		p = p.next
	while q != None:
		if q.data not in l:
			l.append(q.data)
		q = q.next
	l.sort()
	for i in l:
		print(i, end=' ')


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


def union(head1, head2):
	x = set()
	c1 = head1
	while c1:
		x.add(c1.data)
		c1 = c1.next
	c2 = head2
	while c2:
		x.add(c2.data)
		c2 = c2.next
	x = list(x)
	x.sort()
	for i in x:
		print(i, end=' ')


def union(head1, head2):
	x = set()
	temp = head1
	while temp is not None:
		x.add(temp.data)
		temp = temp.next
	temp = head2
	while temp is not None:
		x.add(temp.data)
		temp = temp.next
	ans = list(x)
	ans = sorted(ans)
	i = 1
	head = Node(ans[0])
	temp = head
	while i < len(ans):
		x = Node(ans[i])
		temp.next = x
		temp = x
		i += 1
	return head


def union(head1, head2):
	dic = {}
	new = linkedList()
	n = []
	itr1 = head1
	while itr1:
		if itr1.data not in n:
			n.append(itr1.data)
		itr1 = itr1.next
	itr2 = head2
	while itr2:
		if itr2.data not in n:
			n.append(itr2.data)
		itr2 = itr2.next
	n.sort()
	for i in n:
		print(i, end=' ')


def union(head1, head2):
	itr1 = head1
	itr2 = head2
	l = []
	while itr1:
		l.append(itr1.data)
		itr1 = itr1.next
	while itr2:
		l.append(itr2.data)
		itr2 = itr2.next
	l = set(l)
	l = list(l)
	l.sort()
	ll = linkedList()
	for i in l:
		ll.insert(i)
	return ll.head


def union(head1, head2):
	I = set()
	cur1 = head1
	while cur1:
		I.add(cur1.data)
		cur1 = cur1.next
	cur2 = head2
	while cur2:
		I.add(cur2.data)
		cur2 = cur2.next
	U = sorted(I)
	for i in U:
		print(i, end=' ')


def union(head1, head2):
	s = set()
	while head1:
		s.add(head1.data)
		head1 = head1.next
	while head2:
		s.add(head2.data)
		head2 = head2.next
	s = list(s)
	s.sort()
	start = cur = None
	for i in s:
		tmp = Node(i)
		if start == None:
			start = tmp
			cur = start
		else:
			cur.next = tmp
			cur = tmp
	return start


def union(head1, head2):
	curr = head1
	lis = set()
	while curr:
		lis.add(curr.data)
		curr = curr.next
	curr = head2
	while curr:
		lis.add(curr.data)
		curr = curr.next
	sortedlis = sorted(lis)
	temp = Node('dummy')
	curr = temp
	for i in sortedlis:
		node = Node(i)
		curr.next = node
		curr = curr.next
	return temp.next


def union(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
	l4 = l1 + l2
	l4 = set(l4)
	l3 = list(l4)
	l3.sort()
	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 union(head1, head2):
	s = set()
	while head1:
		s.add(head1.data)
		head1 = head1.next
	while head2:
		s.add(head2.data)
		head2 = head2.next
	l = []
	for i in s:
		l.append(i)
	l.sort()
	l.reverse()
	h1 = Node(l[0])
	l.remove(l[0])
	for i in l:
		node = Node(i)
		node.next = h1
		h1 = node
	return h1


def union(head1, head2):
	s = set()
	curr = head1
	while curr:
		i = curr.data
		if i not in s:
			s.add(i)
		curr = curr.next
	curr = head2
	while curr:
		i = curr.data
		if i not in s:
			s.add(i)
		curr = curr.next
	l = sorted(list(s))
	head = Node(l[0])
	curr = head
	for i in l[1:]:
		curr.next = Node(i)
		curr = curr.next
	return head


def union(head1, head2):
	temp1 = head1
	op = set()
	while temp1.next:
		temp1 = temp1.next
	temp1.next = head2
	temp1 = head1
	while temp1:
		op.add(temp1.data)
		temp1 = temp1.next
	op = sorted(list(op))
	temp1 = head1
	for i in range(len(op)):
		temp1.data = op[i]
		prev = temp1
		temp1 = temp1.next
	prev.next = None
	return head1


def union(head1, head2):
	tek = head1
	arr1 = []
	while tek != None:
		arr1.append(tek.data)
		tek = tek.next
	tek = head2
	while tek != None:
		arr1.append(tek.data)
		tek = tek.next
	arr = set(arr1)
	arr1 = list(arr)
	arr1.sort()
	head3 = Node(0)
	tek = head3
	i = 0
	while i < len(arr1):
		tek.next = Node(arr1[i])
		tek = tek.next
		i += 1
	return head3.next


def union(head1, head2):
	new = set()
	while head2:
		new.add(head2.data)
		head2 = head2.next
	while head1:
		new.add(head1.data)
		head1 = head1.next
	new = list(new)
	new.sort()
	ans = Node(0)
	temp = ans
	for i in range(len(new)):
		curr = Node(new[i])
		temp.next = curr
		temp = curr
	return ans.next


def union(head1, head2):
	s = set()
	while head2:
		s.add(head2.data)
		head2 = head2.next
	while head1:
		s.add(head1.data)
		head1 = head1.next
	s = list(s)
	s.sort()
	ans = Node(-1)
	temp = ans
	for i in range(len(s)):
		new = Node(s[i])
		temp.next = new
		temp = new
	return ans.next


def union(head1, head2):
	a = head1
	b = head2
	v = set()
	while a:
		v.add(a.data)
		a = a.next
	while b:
		v.add(b.data)
		b = b.next
	v = sorted(v)
	dummy = Node(0)
	m = dummy
	for i in v:
		m.next = Node(i)
		m = m.next
	return dummy.next


def union(head1, head2):
	main = set()
	while head1 != None:
		main.add(head1.data)
		head1 = head1.next
	while head2 != None:
		main.add(head2.data)
		head2 = head2.next
	main = sorted(main)
	print(*main, end=' ')
	return None


def union(head1, head2):
	s = set()
	while head1:
		s.add(head1.data)
		head1 = head1.next
	while head2:
		s.add(head2.data)
		head2 = head2.next
	s = list(s)
	s.sort()
	start = None
	for i in s:
		node = Node(i)
		if start == None:
			start = node
			prev = node
		else:
			prev.next = node
			prev = node
	return start


def union(head1, head2):
	(a, b) = ([], [])
	while head1:
		a.append(head1.data)
		head1 = head1.next
	while head2:
		b.append(head2.data)
		head2 = head2.next
	newList = sorted(list(set(a + b)))
	for val in newList:
		print(val, end=' ')


def union(head1, head2):
	(temp1, temp2) = (head1, head2)
	(l1, l2) = ([], [])
	while temp1:
		l1.append(temp1.data)
		temp1 = temp1.next
	while temp2:
		l2.append(temp2.data)
		temp2 = temp2.next
	res = []
	for i in l1:
		if i not in res:
			res.append(i)
	for i in l2:
		if i not in res:
			res.append(i)
	res.sort()
	ll = linkedList()
	for i in res:
		ll.insert(i)
	return ll.head


def union(head1, head2):
	l1 = []
	l2 = []
	curr = head1
	while head1:
		l1.append(head1.data)
		head1 = head1.next
	while head2:
		l1.append(head2.data)
		head2 = head2.next
	l1 = list(set(l1))
	for i in l1:
		l2.append(i)
	l2.sort()
	for i in l2:
		print(i, end=' ')


def union(head1, head2):
	c = {}
	temp1 = head1
	temp2 = head2
	while temp1 != None or temp2 != None:
		if temp1 != None:
			c[temp1.data] = 1
			temp1 = temp1.next
		if temp2 != None:
			c[temp2.data] = 1
			temp2 = temp2.next
	l = linkedList()
	x = sorted(c.keys())
	for i in x:
		l.insert(i)
	return l.head


def union(head1, head2):
	res = {}
	cur = head1
	while cur:
		res[cur.data] = 1
		cur = cur.next
	cur = head2
	while cur:
		res[cur.data] = 1
		cur = cur.next
	r1 = linkedList()
	l1 = sorted(res.keys())
	for item in l1:
		r1.insert(item)
	return r1.head


def union(head1, head2):
	a = []
	b = []
	while head1 is not None:
		a.append(head1.data)
		head1 = head1.next
	while head2 is not None:
		b.append(head2.data)
		head2 = head2.next
	m = sorted(set(a + b))
	for i in m:
		print(i, end=' ')


import heapq

def union(head1, head2):
	h = []
	s = set()
	n = head1
	while n:
		s.add(n.data)
		n = n.next
	n = head2
	while n:
		s.add(n.data)
		n = n.next
	for i in s:
		h.append(i)
	h.sort()
	N = None
	head = None
	for i in h:
		n = Node(i)
		if not head:
			head = n
			N = n
		else:
			N.next = n
			N = n
	return head


def union(head1, head2):
	s = {head1.data}
	tmp = head1.next
	while tmp != None:
		s.add(tmp.data)
		tmp = tmp.next
	tmp = head2
	while tmp != None:
		s.add(tmp.data)
		tmp = tmp.next
	tmp = head1
	x = 0
	for i in sorted(s):
		tmp.data = i
		if tmp.next == None and x < len(s) - 1:
			tmp.next = head2
		if x == len(s) - 1:
			tmp.next = None
			return head1
		tmp = tmp.next
		x += 1


class Node:

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

class Sol:

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

def union(head1, head2):
	ans = Sol()
	l = []
	while head1 is not None:
		l.append(head1.data)
		head1 = head1.next
	while head2 is not None:
		l.append(head2.data)
		head2 = head2.next
	l = sorted(list(set(l)))
	for i in l:
		new = Node(i)
		if ans.head == None:
			ans.head = new
			ans.tail = new
		else:
			ans.tail.next = new
			ans.tail = new
	return ans.head


def union(head1, head2):
	set_elt = {head1.data}
	(res, h) = (head1, head1)
	while head1.next:
		if head1.data not in set_elt:
			set_elt.add(head1.data)
			h.next = head1
			h = h.next
		head1 = head1.next
	if head1.data not in set_elt:
		set_elt.add(head1.data)
		h.next = head1
		h = head1
	while head2.next:
		if head2.data not in set_elt:
			set_elt.add(head2.data)
			h.next = head2
			h = head2
		head2 = head2.next
	if head2.data not in set_elt:
		set_elt.add(head2.data)
		h.next = head2
		h = head2
	h.next = None
	return sortList(res)

def sortList(head):
	if not head or not head.next:
		return head
	(l1, l2) = split(head)
	l1 = sortList(l1)
	l2 = sortList(l2)
	return merge(l1, l2)

def split(l):
	fast = l
	slow = l
	while fast.next and fast.next.next:
		fast = fast.next.next
		slow = slow.next
	temp = slow.next
	slow.next = None
	return (l, temp)

def merge(l1, l2):
	if not l1:
		return l2
	if not l2:
		return l1
	if l1.data <= l2.data:
		res = l1
		l1 = l1.next
	else:
		res = l2
		l2 = l2.next
	h = res
	while l1 and l2:
		if l1.data <= l2.data:
			h.next = l1
			l1 = l1.next
		else:
			h.next = l2
			l2 = l2.next
		h = h.next
	if l1:
		h.next = l1
	if l2:
		h.next = l2
	return res


def union(head1, head2):
	p = head1
	q = head2
	d = set()
	s = set()
	while p != None:
		d.add(p.data)
		p = p.next
	while q:
		s.add(q.data)
		q = q.next
	intersect = d.union(s)
	op = linkedList()
	for e in sorted(intersect):
		op.insert(e)
	return op.head


def union(head1, head2):
	(t, tt) = (head1, head2)
	k = []
	while t:
		if t.data not in k:
			k.append(t.data)
		t = t.next
	while tt:
		if tt.data not in k:
			k.append(tt.data)
		tt = tt.next
	k.sort()
	root = Node(k[0])
	i = 1
	r = root
	while i < len(k):
		y = Node(k[i])
		r.next = y
		r = r.next
		i += 1
	return root


def union(head1, head2):
	l = []
	while head1:
		l.append(head1.data)
		head1 = head1.next
	while head2:
		l.append(head2.data)
		head2 = head2.next
	l = list(set(l))
	l.sort()
	a = Node(-1)
	t = a
	for i in l:
		t.next = Node(i)
		t = t.next
	return a.next


def union(head1, head2):
	l = set()
	while head1 or head2:
		if head1:
			l.add(head1.data)
			head1 = head1.next
		if head2:
			l.add(head2.data)
			head2 = head2.next
	l = sorted(l)
	temp = Node(l[0])
	curr = temp
	i = 1
	while i < len(l):
		temp.next = Node(l[i])
		temp = temp.next
		i += 1
	return curr


def union(head1, head2):
	S = set()
	while head1 != None:
		S.add(head1.data)
		head1 = head1.next
	while head2 != None:
		S.add(head2.data)
		head2 = head2.next
	li = []
	for i in S:
		li.append(i)
	li.sort()
	for i in li:
		print(i, end=' ')


def union(head1, head2):
	p1 = head1
	p2 = head2
	myList = [p1.data, p2.data]
	while p1.next:
		myList.append(p1.next.data)
		p1 = p1.next
	while p2.next:
		myList.append(p2.next.data)
		p2 = p2.next
	myList = sorted(list(set(myList)))
	head3 = Node(myList[0])
	p3 = head3
	for i in range(1, len(myList)):
		p3.next = Node(myList[i])
		p3 = p3.next
	return head3


def union(head1, head2):
	a = []
	b = head1
	h = head2
	while b:
		a.append(b.data)
		b = b.next
	while h:
		a.append(h.data)
		h = h.next
	r = [i for i in set(a)]
	r.sort()
	t = y = Node(r[0])
	for i in range(1, len(r)):
		t.next = Node(r[i])
		t = t.next
	return y


def union(head1, head2):
	a = []
	tmp = head1
	while tmp:
		a.append(tmp.data)
		tmp = tmp.next
	tmp2 = head2
	while tmp2:
		a.append(tmp2.data)
		tmp2 = tmp2.next
	a.sort()
	a = set(a)
	h = None
	hh = None
	for i in sorted(a):
		if not h:
			h = Node(i)
			hh = h
		else:
			h.next = Node(i)
			h = h.next
	return hh


def union(head1, head2):
	ptr = head1
	ptr2 = head2
	s = set()
	li = []
	l = []
	while ptr:
		li.append(ptr.data)
		ptr = ptr.next
	while ptr2:
		li.append(ptr2.data)
		ptr2 = ptr2.next
	l = list(set(li))
	l.sort()
	for i in l:
		print(i, end=' ')


def union(head1, head2):
	setti = set()
	while head1:
		setti.add(head1.data)
		head1 = head1.next
	while head2:
		setti.add(head2.data)
		head2 = head2.next
	head = Node(0)
	start = head
	for item in sorted(setti):
		head.next = Node(item)
		head = head.next
	return start.next


def union(head1, head2):
	union = []
	cur = head1
	while cur:
		union.append(cur.data)
		cur = cur.next
	cur = head2
	while cur:
		union.append(cur.data)
		cur = cur.next
	final = list(set(union))
	final.sort()
	for i in final:
		print(i, end=' ')


def union(head1, head2):
	s = set()
	while head1:
		s.add(head1.data)
		head1 = head1.next
	while head2:
		s.add(head2.data)
		head2 = head2.next
	for i in sorted(s):
		print(i, end=' ')
	return None


def union(head1, head2):
	s = set()
	p = head1
	while p != None:
		if p.data not in s:
			s.add(p.data)
		p = p.next
	p = head2
	while p != None:
		if p.data not in s:
			s.add(p.data)
		p = p.next
	l = list(s)
	l.sort()
	head = None
	for i in l:
		temp = Node(i)
		if head == None:
			head = temp
			p = head
		else:
			p.next = temp
			p = temp
	return head


def union(head1, head2):
	curr = head1
	ans = []
	while curr:
		ans.append(curr.data)
		curr = curr.next
	curr = head2
	while curr:
		ans.append(curr.data)
		curr = curr.next
	union = list(set(ans))
	res = []
	for i in union:
		res.append(i)
	res.sort()
	for i in res:
		print(i, end=' ')


def union(head1, head2):
	us = set()
	us2 = set()
	ptr = head1
	ptr2 = head2
	while ptr is not None:
		us.add(ptr.data)
		ptr = ptr.next
	while ptr2 is not None:
		us2.add(ptr2.data)
		ptr2 = ptr2.next
	l = us.union(us2)
	l = list(l)
	l.sort()
	head3 = None
	for i in range(len(l)):
		if i == 0:
			head3 = Node(l[i])
			ptr = head3
		else:
			extra = Node(l[i])
			ptr.next = extra
			ptr = extra
	return head3


def union(head1, head2):
	l = set()
	if head1:
		temp1 = head1
		while temp1:
			l.add(temp1.data)
			temp1 = temp1.next
	if head2:
		temp2 = head2
		while temp2:
			l.add(temp2.data)
			temp2 = temp2.next
	s = list(l)
	s.sort()
	head = None
	tail = None
	while s:
		a = s.pop(0)
		n = Node(a)
		if head == None:
			head = n
			tail = n
		else:
			tail.next = n
			tail = tail.next
	return head


def length(head):
	itr = head
	a = []
	while itr:
		a.append(itr.data)
		itr = itr.next
	return a

def join_linked_list(h1, h2):
	if h1 == None and h2 == None:
		return None
	if h1 == None:
		return h2
	if h2 == None:
		return h1
	temp = None
	if h1.data < h2.data:
		temp = h1
		temp.next = union(h1.next, h2)
	elif h2.data < h1.data:
		temp = h2
		temp.next = union(h1, h2.next)
	elif h1.data == h2.data:
		temp = h1
		temp.next = union(h1.next, h2.next)
	return temp

def sorting_linked_list(head):
	a = []
	itr = head
	while itr:
		a.append(itr.data)
		itr = itr.next
	a = list(set(a))
	a.sort()
	return list_to_linked_list(a)

def list_to_linked_list(a):
	n = len(a)
	head = None
	for i in range(n - 1, -1, -1):
		new = Node(a[i])
		new.next = head
		head = new
	return head

def union(h1, h2):
	h1 = sorting_linked_list(h1)
	h2 = sorting_linked_list(h2)
	return join_linked_list(h1, h2)
	return h2


def union(head1, head2):

	def data(head):
		temp = head
		d = list()
		while temp:
			d.append(temp.data)
			temp = temp.next
		return d
	d1 = data(head1)
	d2 = data(head2)
	d = list(set(d1 + d2))
	d.sort()
	head = Node(0)
	curr = head
	for i in d:
		curr.next = Node(i)
		curr = curr.next
	return head.next


def union(head1, head2):
	l = []
	curr = head1
	curr1 = head2
	while curr is not None:
		l.append(curr.data)
		curr = curr.next
	while curr1 is not None:
		l.append(curr1.data)
		curr1 = curr1.next
	x = list(set(l))
	x.sort()
	for i in x:
		print(i, end=' ')


def union(head1, head2):
	arr = set()
	cur1 = head1
	cur2 = head2
	while cur1:
		arr.add(cur1.data)
		cur1 = cur1.next
	while cur2:
		arr.add(cur2.data)
		cur2 = cur2.next
	arr = list(arr)
	arr.sort()
	head = Node(0)
	cur = head
	for i in range(len(arr)):
		cur.next = Node(arr[i])
		cur = cur.next
	return head.next