Given two linked lists, the task is to complete the function findIntersection(), that returns the intersection of two linked lists. Each of the two linked list contains distinct node values.
Example 1:
Input:
LinkedList1: 9->6->4->2->3->8
LinkedList2: 1->2->8->6
Output: 6 2 8
Your Task:
You task is to complete the function findIntersection() which takes the heads of the 2 input linked lists as parameter and returns the head of intersection list. Returned list will be automatically printed by driver code.
Note: The order of nodes in this list should be same as the order in which those particular nodes appear in input list 1.
Constraints:
1 <= n,m <= 10^{4}
Expected time complexity: O(m+n)
Expected auxiliary space: O(m+n)

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Sorting

Data structures

Starter code: #User function Template for python3

''' structure of list node:

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

'''

class Solution:
    def findIntersection(self, head1, head2):
        # code here
        # return head of intersection list

Solutions:
class Solution:

	def findIntersection(self, head1, head2):
		l = set()
		temp = head1
		while head2:
			l.add(head2.data)
			head2 = head2.next
		dummy = Node(-1)
		p = dummy
		while head1:
			if head1.data in l:
				dummy.next = head1
				dummy = dummy.next
			head1 = head1.next
		dummy.next = None
		return p.next


class Solution:

	def findIntersection(self, head1, head2):
		l = set()
		while head2:
			l.add(head2.data)
			head2 = head2.next
		p = Node(0)
		curr = p
		while head1:
			if head1.data in l:
				p.next = head1
				p = p.next
			head1 = head1.next
		p.next = None
		return curr.next


class Solution:

	def findIntersection(self, head1, head2):
		mapp = {}
		curr2 = head2
		while curr2:
			mapp[curr2.data] = 1
			curr2 = curr2.next
		curr1 = head1
		dummynode = Node(None)
		curr = dummynode
		while curr1:
			if curr1.data in mapp:
				curr.next = Node(curr1.data)
				curr = curr.next
			curr1 = curr1.next
		return dummynode.next


from collections import Counter

class Solution:

	def findIntersection(self, head1, head2):
		c = {}
		cur1 = head1
		cur2 = head2
		res = []
		while cur2:
			c[cur2.data] = 1
			cur2 = cur2.next
		while cur1:
			if cur1.data in c:
				res.append(cur1.data)
			cur1 = cur1.next
		n = Node(0)
		h = n
		for i in res:
			k = Node(i)
			n.next = k
			n = n.next
		return h.next


class Solution:

	def findIntersection(self, head1, head2):
		hash = set()
		while head2:
			hash.add(head2.data)
			head2 = head2.next
		new_node = Node(0)
		temp = new_node
		while head1:
			if head1.data in hash:
				temp.next = Node(head1.data)
				temp = temp.next
			head1 = head1.next
		return new_node.next


class Solution:

	def findIntersection(self, head1, head2):
		cur1 = head2
		cur2 = head1
		l = linkedList()
		s = set()
		while cur1:
			s.add(cur1.data)
			cur1 = cur1.next
		while cur2:
			if cur2.data in s:
				l.insert(cur2.data)
			cur2 = cur2.next
		return l.head


class Solution:

	def findIntersection(self, head1, head2):
		curr_node = head2
		temp_lst = set()
		while curr_node:
			temp_lst.add(curr_node.data)
			curr_node = curr_node.next
		L2 = linkedList()
		L2.head = None
		next_node = L2.head
		curr_node = head1
		while curr_node:
			if curr_node.data in temp_lst:
				new_node = Node(curr_node.data)
				if next_node is None:
					L2.head = new_node
					new_node.next = None
					next_node = L2.head
				else:
					next_node.next = new_node
					new_node.next = None
					next_node = new_node
			curr_node = curr_node.next
		return L2.head


class Solution:

	def findIntersection(self, head1, head2):
		h2 = set()
		while head2:
			h2.add(head2.data)
			head2 = head2.next
		tmp = Node(-1)
		dum = tmp
		while head1:
			if head1.data in h2:
				tmp.next = head1
				tmp = tmp.next
			head1 = head1.next
		tmp.next = None
		return dum.next


class Solution:

	def findIntersection(self, head1, head2):
		dict_ = set()
		x = []
		while head2:
			dict_.add(head2.data)
			head2 = head2.next
		p = Node(-1)
		dummy = p
		while head1:
			if head1.data in dict_:
				p.next = head1
				p = p.next
			head1 = head1.next
		p.next = None
		return dummy.next


class Solution:

	def findIntersection(self, headA, headB):
		s = set()
		while headB:
			s.add(headB.data)
			headB = headB.next
		p = Node(-1)
		dummy = p
		while headA:
			if headA.data in s:
				p.next = headA
				p = p.next
			headA = headA.next
		p.next = None
		return dummy.next


class Node:

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

class Solution:

	def findIntersection(self, head1, head2):
		sett = set()
		while head2:
			sett.add(head2.data)
			head2 = head2.next
		node = Node(-1)
		temp = node
		while head1:
			if head1.data in sett:
				node.next = head1
				node = node.next
			head1 = head1.next
		node.next = None
		return temp.next


class Solution:

	def findIntersection(self, head1, head2):
		d = dict()
		a = head2
		while a != None:
			if a.data in d:
				d[a.data] += 1
			else:
				d[a.data] = 1
			a = a.next
		a = head1
		ptr = Node(-1)
		temp = ptr
		while a != None:
			if a.data in d:
				t = Node(a.data)
				temp.next = t
				temp = t
			a = a.next
		return ptr.next


class Solution:

	def findIntersection(self, head1, head2):
		s = set()
		temp = head2
		while temp != None:
			s.add(temp.data)
			temp = temp.next
		temp = head1
		res = None
		prev = None
		c = 0
		while temp != None:
			if temp.data in s:
				node = Node(temp.data)
				if c == 0:
					res = node
					prev = node
					c += 1
				else:
					prev.next = node
					prev = node
			temp = temp.next
		return res


class Solution:

	def findIntersection(self, head1, head2):
		h = {}
		listt = None
		listtend = None
		temp = head2
		if temp == None:
			return None
		while temp:
			if temp.data not in h:
				h[temp.data] = 1
			temp = temp.next
		temp1 = head1
		while temp1:
			if temp1.data in h:
				if listt == None:
					listt = temp1
					listtend = temp1
				else:
					listtend.next = temp1
					listtend = listtend.next
			temp1 = temp1.next
		listtend.next = None
		return listt


class Solution:

	def findIntersection(self, head1, head2):
		a = set()
		while head2:
			a.add(head2.data)
			head2 = head2.next
		temp = Node(-1)
		temp2 = temp
		while head1:
			if head1.data in a:
				temp.next = head1
				temp = temp.next
			head1 = head1.next
		temp.next = None
		return temp2.next


class Solution:

	def findIntersection(self, head1, head2):
		(head1, head2) = (head2, head1)
		hashmap = {}
		while head1 != None:
			data = head1.data
			if data not in hashmap.keys():
				hashmap[data] = 1
			head1 = head1.next
		ans = linkedList()
		while head2 != None:
			data = head2.data
			if data in hashmap.keys():
				ans.insert(data)
			head2 = head2.next
		return ans.head


class Solution:

	def findIntersection(self, head1, head2):
		dt = {}
		a = head1
		b = head2
		start = temp = Node(None)
		while b:
			if b.data not in dt:
				dt[b.data] = True
			b = b.next
		while a:
			if a.data in dt:
				new = Node(a.data)
				temp.next = new
				temp = temp.next
			a = a.next
		return start.next


class Solution:

	def findIntersection(self, head1, head2):
		if head1 is None or head2 is None:
			return None
		set1 = set()
		node2 = head2
		while node2:
			set1.add(node2.data)
			node2 = node2.next
		node1 = head1
		head3 = None
		node3 = None
		while node1:
			if node1.data in set1:
				if head3 is None:
					node = Node(node1.data)
					head3 = node
					node3 = head3
				else:
					node = Node(node1.data)
					node3.next = node
					node3 = node3.next
			node1 = node1.next
		return head3


class Solution:

	def findIntersection(self, head1, head2):
		a = head1
		b = head2
		l = set()
		while b != None:
			l.add(b.data)
			b = b.next
		while a != None:
			if a.data in l:
				print(a.data, end=' ')
			a = a.next


class Solution:

	def findIntersection(self, head1, head2):
		a = []
		while head2 is not None:
			a.append(head2.data)
			head2 = head2.next
		d = dict()
		for ele in a:
			d[ele] = 0
		for ele in a:
			d[ele] = d[ele] + 1
		arr = []
		while head1 is not None:
			arr.append(head1.data)
			head1 = head1.next
		k = []
		for ele in arr:
			if ele in d.keys():
				k.append(ele)
		k.append('x')
		head = None
		tail = None
		for ele in k:
			if ele != 'x':
				if head is None:
					newnode = Node(ele)
					head = newnode
					tail = newnode
				else:
					newnode = Node(ele)
					tail.next = newnode
					tail = newnode
		return head


class Solution:

	def findIntersection(self, head1, head2):
		unique = set()
		dummy = Node(0)
		head3 = dummy
		while head2:
			unique.add(head2.data)
			head2 = head2.next
		while head1:
			if head1.data in unique:
				new = Node(head1.data)
				dummy.next = new
				dummy = dummy.next
			head1 = head1.next
		return head3.next


class Solution:

	def findIntersection(self, head1, head2):
		s = set()
		while head2:
			s.add(head2.data)
			head2 = head2.next
		newhead = None
		newtail = None
		while head1:
			if head1.data in s:
				if newhead is None:
					newhead = newtail = Node(head1.data)
				else:
					newtail.next = Node(head1.data)
					newtail = newtail.next
			head1 = head1.next
		return newhead


class Solution:

	def findIntersection(self, head1, head2):
		uset = set()
		curr = head2
		while curr:
			uset.add(curr.data)
			curr = curr.next
		tail = head1
		new_head = None
		prev = None
		while tail != None:
			if tail.data in uset:
				if new_head == None:
					new_head = prev = Node(tail.data)
				else:
					prev.next = Node(tail.data)
					prev = prev.next
			tail = tail.next
		return new_head


class Solution:

	def findIntersection(self, head1, head2):
		l = set()
		if head1 == None or head2 == None:
			return None
		dummy = Node(-1)
		end = dummy
		while head2 != None:
			l.add(head2.data)
			head2 = head2.next
		while head1 != None:
			if head1.data in l:
				end.next = head1
				end = end.next
			head1 = head1.next
		end.next = None
		return dummy.next


class Solution:

	def find(self, l2, data):
		while l2:
			if l2.data == data:
				return True
			l2 = l2.next
		return False

	def findIntersection(self, head1, head2):
		ret_head = None
		ret_current = None
		current = head1
		l2s = set()
		while head2:
			l2s.add(head2.data)
			head2 = head2.next
		while current:
			if current.data in l2s:
				ret_node = Node(current.data)
				if not ret_current:
					ret_head = ret_node
					ret_current = ret_head
				else:
					ret_current.next = ret_node
					ret_current = ret_node
			current = current.next
		return ret_head


class Solution:

	def findIntersection(self, head1, head2):
		ans = []
		while head2:
			ans.append(head2.data)
			head2 = head2.next
		ans = set(ans)
		temp = Node(-1)
		res = temp
		while head1:
			if head1.data in ans:
				temp.next = head1
				temp = temp.next
			head1 = head1.next
		temp.next = None
		return res.next


class Solution:

	def findIntersection(self, head1, head2):
		slist = set()
		while head2 != None:
			slist.add(head2.data)
			head2 = head2.next
		newhead = Node(-1)
		temp = newhead
		while head1 != None:
			if head1.data in slist:
				newhead.next = head1
				newhead = newhead.next
			head1 = head1.next
		newhead.next = None
		return temp.next


class Solution:

	def findIntersection(self, head1, head2):
		l = set()
		cur2 = head2
		while cur2:
			l.add(cur2.data)
			cur2 = cur2.next
		cur1 = head1
		result_head = Node(None)
		result_tail = result_head
		while cur1:
			if cur1.data in l:
				result_head.next = cur1
				result_head = result_head.next
			cur1 = cur1.next
		result_head.next = None
		return result_tail.next


class Solution:

	def findIntersection(self, head1, head2):
		rec = set()
		while head2:
			rec.add(head2.data)
			head2 = head2.next
		res = linkedList()
		while head1:
			if head1.data in rec:
				res.insert(head1.data)
			head1 = head1.next
		return res.head


class Solution:

	def findIntersection(self, head1, head2):
		map = {}
		curr = head2
		while curr is not None:
			if curr.data in map:
				map[curr.data] += 1
			else:
				map[curr.data] = 1
			curr = curr.next
		curr = head1
		l = []
		while curr is not None:
			if curr.data in map:
				l.append(curr.data)
			curr = curr.next
		head = Node(l[0])
		curr = head
		for i in range(1, len(l)):
			newNode = Node(l[i])
			curr.next = newNode
			curr = curr.next
		return head


class Solution:

	def findIntersection(self, head1, head2):
		l = Node(0)
		m = l
		hashset = set()
		while head2:
			hashset.add(head2.data)
			head2 = head2.next
		while head1:
			if head1.data in hashset:
				hashset.remove(head1.data)
				m.next = head1
				head1 = head1.next
				m = m.next
				continue
			head1 = head1.next
		m.next = None
		return l.next


class Solution:

	def findIntersection(self, head1, head2):
		hash_map = {}
		while head2:
			hash_map[head2.data] = head2
			head2 = head2.next
		new_head = temp_node = None
		while head1:
			if head1.data in hash_map:
				new_node = Node(head1.data)
				if new_head is None:
					new_head = temp_node = new_node
				else:
					temp_node.next = new_node
					temp_node = new_node
			head1 = head1.next
		return new_head


class Solution:

	def findIntersection(self, head1, head2):
		s = set()
		while head2:
			s.add(head2.data)
			head2 = head2.next
		result = []
		while head1:
			if head1.data in s:
				result.append(head1.data)
			head1 = head1.next
		dummy = Node('dummy')
		curr = dummy
		for x in result:
			curr.next = Node(x)
			curr = curr.next
		return dummy.next


class Solution:

	def findIntersection(self, head1, head2):
		if head1 is None or head2 is None:
			return None
		else:
			x = set()
			curr2 = head2
			while curr2:
				x.add(curr2.data)
				curr2 = curr2.next
			p = Node(-1)
			dummy = p
			while head1:
				if head1.data in x:
					p.next = head1
					p = p.next
				head1 = head1.next
			p.next = None
			return dummy.next


class Solution:

	def findIntersection(self, head1, head2):
		s = set()
		while head2:
			s.add(head2.data)
			head2 = head2.next
		nnode = Node(-1)
		dummy = nnode
		while head1:
			if head1.data in s:
				nnode.next = head1
				nnode = nnode.next
			head1 = head1.next
		nnode.next = None
		return dummy.next


class Solution:

	def findIntersection(self, head1, head2):
		current1 = head2
		current2 = head1
		values = set()
		while current1 is not None:
			values.add(current1.data)
			current1 = current1.next
		dummy = Node(0)
		tail = dummy
		while current2 is not None:
			if current2.data in values:
				tail.next = Node(current2.data)
				tail = tail.next
			current2 = current2.next
		return dummy.next


class Solution:

	def findIntersection(self, head1, head2):
		a = set()
		while head2:
			a.add(head2.data)
			head2 = head2.next
		l = linkedList()
		while head1:
			if head1.data in a:
				l.insert(head1.data)
			head1 = head1.next
		return l.head


class Solution:

	def findIntersection(self, head1, head2):
		res = []
		ans = Node(123)
		a = ans
		l1 = head2
		vis = set()
		while l1:
			vis.add(l1.data)
			l1 = l1.next
		l2 = head1
		while l2:
			target = l2.data
			if target in vis:
				a.next = Node(l2.data)
				a = a.next
			l2 = l2.next
		return ans.next


class Solution:

	def findIntersection(self, head1, head2):
		st = set()
		while head2:
			st.add(head2.data)
			head2 = head2.next
		newHead = None
		newTail = None
		while head1:
			if head1.data in st:
				if newHead is None:
					newHead = newTail = Node(head1.data)
				else:
					newTail.next = Node(head1.data)
					newTail = newTail.next
			head1 = head1.next
		return newHead


class Node:

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

class Solution:

	def findIntersection(self, head1, head2):
		cur1 = head1
		cur2 = head2
		a = set()
		while cur2 != None:
			a.add(cur2.data)
			cur2 = cur2.next
		temp = Node(-1)
		dummy = temp
		while cur1 != None:
			c = cur1.data
			if c in a:
				temp.next = cur1
				temp = temp.next
			cur1 = cur1.next
		temp.next = None
		return dummy.next


class Solution:

	def findIntersection(self, head1, head2):
		(li1, li2) = ([], [])
		(t1, t2) = (head1, head2)
		d = {}
		while t2 != None:
			d[t2.data] = 1
			t2 = t2.next
		while t1 != None:
			li1.append(t1.data)
			t1 = t1.next
		n = Node(0)
		l = n
		for i in li1:
			if i in d:
				n.next = Node(i)
				n = n.next
		return l.next


class Solution:

	def findIntersection(self, head1, head2):
		d = dict()
		dd = dict()
		while head2:
			dd[head2.data] = head2.data
			head2 = head2.next
		l = []
		while head1:
			if head1.data in dd.keys():
				l.append(head1.data)
			head1 = head1.next
		ls = linkedList()
		for u in l:
			ls.insert(u)
		return ls.head


class Solution:

	def findIntersection(self, head1, head2):
		tmp = head2
		b = {}
		while tmp:
			if tmp.data in b:
				b[tmp.data] = 1
			else:
				b[tmp.data] = 1
			tmp = tmp.next
		tmp1 = head1
		c = []
		tmp = head1
		prev = tmp
		while tmp1:
			if tmp1.data in b:
				tmp.data = tmp1.data
				if tmp.next == None and tmp1.next != None:
					tmp.next = head2
				if tmp1.next == None:
					tmp.next = None
					return head1
				prev = tmp
				tmp = tmp.next
			if tmp1.next == None:
				prev.next = None
				return head1
			tmp1 = tmp1.next


class Solution:

	def findIntersection(self, head1, head2):
		hash = {}
		head = None
		while head2:
			hash[head2.data] = 1
			head2 = head2.next
		while head1:
			if head1.data in hash.keys():
				temp = Node(head1.data)
				if not head:
					head = temp
					tail = temp
				else:
					tail.next = temp
					tail = tail.next
			head1 = head1.next
		return head


class Solution:

	def findIntersection(self, head1, head2):
		mp = {}
		while head2:
			mp[head2.data] = 1
			head2 = head2.next
		tmp = Node(-1)
		head = tmp
		while head1:
			if head1.data in mp.keys():
				tmp.next = Node(head1.data)
				tmp = tmp.next
			head1 = head1.next
		tmp.next = None
		return head.next


class Solution:

	def findIntersection(self, head1, head2):
		dumm = Node(0)
		x = dumm
		common = set()
		temp = head2
		while temp:
			common.add(temp.data)
			temp = temp.next
		temp = head1
		while temp:
			if temp.data in common:
				dumm.next = Node(temp.data)
				dumm = dumm.next
			temp = temp.next
		return x.next


class Solution:

	def findIntersection(self, head1, head2):
		curr = head2
		visit = set()
		while curr:
			visit.add(curr.data)
			curr = curr.next
		new_node = Node(0)
		tmp = new_node
		while head1:
			if head1.data in visit:
				tmp.next = Node(head1.data)
				tmp = tmp.next
			head1 = head1.next
		tmp.next = None
		return new_node.next


class Solution:

	def findIntersection(self, head1, head2):
		ans = Node(-1)
		temp = ans
		s = set()
		while head2:
			s.add(head2.data)
			head2 = head2.next
		while head1:
			if head1.data in s:
				temp.next = Node(head1.data)
				temp = temp.next
			head1 = head1.next
		return ans.next


class Solution:

	def findIntersection(self, head1, head2):
		x = set()
		while head2:
			x.add(head2.data)
			head2 = head2.next
		y = []
		while head1:
			if head1.data in x:
				y.append(head1.data)
				head1 = head1.next
			else:
				head1 = head1.next
		head3 = Node(y[0])
		cur = head3
		for i in range(1, len(y)):
			p = Node(y[i])
			cur.next = p
			cur = p
		return head3


class Solution:

	def findIntersection(self, head1, head2):
		temp = head2
		s = set()
		while temp is not None:
			s.add(temp.data)
			temp = temp.next
		temp = head1
		arr = []
		while temp is not None:
			if temp.data in s:
				arr.append(temp.data)
			temp = temp.next
		if len(arr) == 0:
			return None
		head = Node(arr[0])
		temp = head
		for i in range(1, len(arr)):
			x = Node(arr[i])
			temp.next = x
			temp = temp.next
		return head


class Solution:

	def findIntersection(self, head1, head2):
		list1_set = set()
		linked_list = linkedList()
		while head2 is not None:
			list1_set.add(head2.data)
			head2 = head2.next
		while head1 is not None:
			if head1.data in list1_set:
				linked_list.insert(head1.data)
			head1 = head1.next
		return linked_list.head


class Solution:

	def findIntersection(self, head1, head2):
		list = []
		s = set()
		current = head2
		while current:
			s.add(current.data)
			current = current.next
		current = head1
		while current:
			if current.data in s:
				list.append(current.data)
			current = current.next
		head = None
		tail = None
		for i in list:
			if head == None:
				head = Node(i)
				tail = Node(i)
				current = head
			else:
				new_node = Node(i)
				current.next = new_node
				current = current.next
		return head


class Solution:

	def findIntersection(self, head1, head2):
		s = set()
		while head2:
			s.add(head2.data)
			head2 = head2.next
		start = cur = None
		while head1:
			if head1.data in s:
				ptr = Node(head1.data)
				if start == None:
					start = ptr
					cur = start
				else:
					cur.next = ptr
					cur = ptr
			head1 = head1.next
		return start


class Solution:

	def findIntersection(self, head1, head2):
		kmap = set()
		ptr = head2
		while ptr:
			kmap.add(ptr.data)
			ptr = ptr.next
		ptr = head1
		ans = Node(-1)
		a = ans
		while ptr:
			if ptr.data in kmap:
				a.next = ptr
				ptr = ptr.next
				a = a.next
				a.next = None
			else:
				ptr = ptr.next
		return ans.next


class Solution:

	def findIntersection(self, head1, head2):
		dic = {}
		res = None
		headnew = None
		while head2 != None:
			dic[head2.data] = 1
			head2 = head2.next
		while head1 != None:
			if head1.data in dic.keys():
				if res == None:
					res = head1
					headnew = res
					nxt = head1.next
					head1.next = None
					head1 = nxt
				else:
					res.next = head1
					res = res.next
					nxt = head1.next
					head1.next = None
					head1 = nxt
			else:
				head1 = head1.next
		return headnew


class Solution:

	def findIntersection(self, head1, head2):
		d = dict()
		(t1, t2) = (head1, head2)
		while t2 != None:
			d[t2.data] = 1
			t2 = t2.next
		head = None
		k = None
		while t1 != None:
			if t1.data in d:
				if not head:
					head = Node(t1.data)
					k = head
				else:
					head.next = Node(t1.data)
					head = head.next
			t1 = t1.next
		return k


class Solution:

	def findIntersection(self, head1, head2):
		nodeSet = set()
		newHead = None
		first = True
		while head2 != None:
			nodeSet.add(head2.data)
			head2 = head2.next
		while head1 != None:
			if head1.data in nodeSet:
				if first == True:
					first = False
					newHead = Node(head1.data)
					temp = newHead
				else:
					temp.next = Node(head1.data)
					temp = temp.next
			head1 = head1.next
		return newHead


class Solution:

	def findIntersection(self, head1, head2):
		set2 = set()
		res = Node(-1)
		curr = res
		while head2 != None:
			set2.add(head2.data)
			head2 = head2.next
		while head1 != None:
			if head1.data in set2:
				curr.next = head1
				curr = curr.next
			head1 = head1.next
		curr.next = None
		return res.next


class Solution:

	def findIntersection(self, head1, head2):
		dummy = Node(-1)
		temp = dummy
		se = set()
		while head2:
			se.add(head2.data)
			head2 = head2.next
		while head1:
			if head1.data in se:
				temp.next = Node(head1.data)
				temp = temp.next
			head1 = head1.next
		return dummy.next


from collections import defaultdict

class Solution:

	def findIntersection(self, head1, head2):
		mp = defaultdict(list)
		nd = head2
		while nd:
			mp[nd.data].append(nd)
			nd = nd.next
		nd = head1
		prehead = Node(-1)
		pre = prehead
		while nd:
			if nd.data in mp:
				pre.next = mp[nd.data].pop()
				pre = pre.next
				pre.next = None
			nd = nd.next
		return prehead.next


class Solution:

	def findIntersection(self, head1, head2):
		d = {}
		while head2 != None:
			data = head2.data
			if data not in d.keys():
				d[data] = 1
			head2 = head2.next
		x = linkedList()
		while head1 != None:
			data = head1.data
			if data in d.keys():
				x.insert(data)
			head1 = head1.next
		return x.head


class Solution:

	def findIntersection(self, head1, head2):
		d = {}
		if head2:
			t = head2
			while t:
				if t.data not in d:
					d[t.data] = 1
				else:
					d[t.data] += 1
				t = t.next
		h = None
		n = None
		if head1:
			t = head1
			while t:
				if d.get(t.data):
					if d.get(t.data) > 0:
						node = Node(t.data)
						if h == None:
							h = node
							n = node
						else:
							n.next = node
							n = node
				t = t.next
		return h


class Solution:

	def findIntersection(self, head1, head2):
		l2 = []
		while head2:
			l2.append(head2.data)
			head2 = head2.next
		temp = new = Node(0)
		l2 = set(l2)
		while head1:
			if head1.data in l2:
				temp.next = Node(head1.data)
				temp = temp.next
			head1 = head1.next
		return new.next


class Solution:

	def findIntersection(self, head1, head2):
		hashSet = set()
		temp2 = head2
		while temp2:
			hashSet.add(temp2.data)
			temp2 = temp2.next
		dummy = head = Node(-1)
		temp1 = head1
		while temp1:
			if temp1.data in hashSet:
				head.next = Node(temp1.data)
				head = head.next
			temp1 = temp1.next
		return dummy.next


class Solution:

	def findIntersection(self, head1, head2):
		set2 = set()
		node = head2
		while node:
			set2.add(node.data)
			node = node.next
		output = None
		tail = None
		node = head1
		while node:
			if node.data in set2:
				if output:
					tail.next = Node(node.data)
					tail = tail.next
				else:
					output = Node(node.data)
					tail = output
			node = node.next
		return output


class Solution:

	def findIntersection(self, head1, head2):
		tail = Node(0)
		tail.next = None
		dummy = tail
		s = set()
		while head2:
			if head2.data not in s:
				s.add(head2.data)
			head2 = head2.next
		while head1:
			if head1.data in s:
				tail.next = Node(head1.data)
				tail = tail.next
			head1 = head1.next
		return dummy.next