Given two linked lists sorted in increasing order, create a new linked list representing the intersection of the two linked lists. The new linked list should be made with its own memory the original lists should not be changed.
Note: The linked list elements are not necessarily distinct.
Example 1:
Input:
L1 = 1->2->3->4->6
L2 = 2->4->6->8
Output: 2 4 6
Explanation: For the given first two
linked list, 2, 4 and 6 are the elements
in the intersection.
Example 2:
Input:
L1 = 10->20->40->50
L2 = 15->40
Output: 40
Your Task:
The task is to complete the function intersection() which should find the intersection of two linked list and add all the elements in intersection to the third linked list and return the head of the third linked list.
Expected Time Complexity : O(n+m)
Expected Auxilliary Space : O(n+m)
Note: n,m are the size of the linked lists.
Constraints:
1 <= size of linked lists <= 5000
1 <= Data in linked list nodes <= 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: #User function Template for python3



''' structure of node:



class Node:

    def __init__(self,data):

        self.data=data

        self.next=None



'''



def findIntersection(head1,head2):

    #return head

Solutions:
def findIntersection(head1, head2):
	ans = Node(123)
	p = ans
	p1 = head1
	p2 = head2
	while p1 and p2:
		if p1.data == p2.data:
			p.next = p1
			p = p1
			p1 = p1.next
			p2 = p2.next
		elif p1.data > p2.data:
			p2 = p2.next
		else:
			p1 = p1.next
	p.next = None
	return ans.next


def findIntersection(head1, head2):
	dummy = head = None
	while head1 and head2:
		if head1.data < head2.data:
			head1 = head1.next
		elif head1.data > head2.data:
			head2 = head2.next
		else:
			if not head:
				dummy = head = Node(head1.data)
			else:
				head.next = Node(head1.data)
				head = head.next
			head1 = head1.next
			head2 = head2.next
	return dummy


def findIntersection(head1, head2):
	itr1 = head1
	itr2 = head2
	tmp = Node(0)
	temp = tmp
	while itr1 and itr2:
		if itr1.data == itr2.data:
			tmp.next = Node(itr1.data)
			tmp = tmp.next
		if itr1.data < itr2.data:
			itr1 = itr1.next
		elif itr1.data == itr2.data:
			itr1 = itr1.next
			itr2 = itr2.next
		else:
			itr2 = itr2.next
	return temp.next


def findIntersection(head1, head2):
	a = []
	c1 = head1
	c2 = head2
	while c1 and c2:
		if c1.data == c2.data:
			a.append(c1.data)
			c1 = c1.next
			c2 = c2.next
		elif c1.data > c2.data:
			c2 = c2.next
		else:
			c1 = c1.next
	d = Node(0)
	new_curr = d
	for i in a:
		new_curr.next = Node(i)
		new_curr = new_curr.next
	return d.next


def findIntersection(head1, head2):
	res = Node(123)
	p = res
	a = head1
	b = head2
	while a and b:
		if a.data == b.data:
			p.next = a
			p = a
			a = a.next
			b = b.next
		elif a.data > b.data:
			b = b.next
		else:
			a = a.next
	p.next = None
	return res.next


def findIntersection(head1, head2):
	new_head = Node(-1)
	temp = new_head
	while head1 != None and head2 != None:
		if head1.data == head2.data:
			temp.next = head1
			temp = temp.next
			head1 = head1.next
			head2 = head2.next
		elif head1.data < head2.data:
			head1 = head1.next
		else:
			head2 = head2.next
		temp.next = None
	return new_head.next


def findIntersection(head1, head2):
	seen = {}
	curr = head1
	curr2 = head2
	intersect = []
	prev = head1
	if head1 == None or head2 == None:
		return -1
	while curr != None:
		if curr.data in seen:
			seen[curr.data] += 1
		else:
			seen[curr.data] = 1
		curr = curr.next
	while curr2 != None:
		if curr2.data in seen:
			if seen[curr2.data] > 0:
				seen[curr2.data] -= 1
				intersect.append(curr2.data)
		curr2 = curr2.next
	ll3 = linkedList()
	for i in intersect:
		ll3.insert(i)
	return ll3.head


def findIntersection(head1, head2):
	ans = None
	cur = None
	if head1.data > head2.data:
		(head1, head2) = (head2, head1)
	(n1, n2) = (head1, head2)
	while n1 and n2:
		if n1.data < n2.data:
			n1 = n1.next
		elif n1.data > n2.data:
			n2 = n2.next
		else:
			nd = Node(n1.data)
			if not ans:
				ans = nd
				cur = nd
			else:
				cur.next = nd
				cur = nd
			n1 = n1.next
			n2 = n2.next
	return ans


def findIntersection(head1, head2):
	front1 = head1
	front2 = head2
	result = res_head = None
	while front1 is not None and front2 is not None:
		node = None
		if front1.data == front2.data:
			node = Node(front1.data)
			front1 = front1.next
			front2 = front2.next
		elif front1.data < front2.data:
			front1 = front1.next
		else:
			front2 = front2.next
		if node:
			if result is None:
				res_head = result = node
			else:
				result.next = node
				result = result.next
	return res_head


def findIntersection(head1, head2):
	dummynode = Node(None)
	curr = dummynode
	(temp1, temp2) = (head1, head2)
	while temp1 != None and temp2 != None:
		if temp1.data == temp2.data:
			newnode = Node(temp1.data)
			curr.next = newnode
			curr = curr.next
			temp1 = temp1.next
			temp2 = temp2.next
		elif temp1.data < temp2.data:
			temp1 = temp1.next
		else:
			temp2 = temp2.next
	return dummynode.next


def findIntersection(head1, head2):
	(p, q) = (head1, head2)
	h = None
	t = None
	while p and q:
		if p.data == q.data:
			new_Node = Node(p.data)
			if h is None:
				h = new_Node
				t = new_Node
			else:
				t.next = new_Node
				t = new_Node
			p = p.next
			q = q.next
		elif p.data < q.data:
			p = p.next
		else:
			q = q.next
	return h


def findIntersection(head1, head2):
	p1 = head1
	p2 = head2
	t = Node(0)
	k = t
	while p1 and p2:
		if p1.data == p2.data:
			t.next = Node(p1.data)
			t = t.next
			p1 = p1.next
			p2 = p2.next
		elif p1.data < p2.data:
			p1 = p1.next
		elif p1.data > p2.data:
			p2 = p2.next
	return k.next


def findIntersection(head1, head2):
	head3 = Node(-1)
	h3 = head3
	while head1 != None and head2 != None:
		if head1.data > head2.data:
			head2 = head2.next
		elif head2.data > head1.data:
			head1 = head1.next
		else:
			h3.next = Node(head1.data)
			h3 = h3.next
			head1 = head1.next
			head2 = head2.next
	return head3.next


def findIntersection(head1, head2):
	ans = Node(123)
	p = ans
	temp1 = head1
	temp2 = head2
	while temp1 and temp2:
		if temp1.data == temp2.data:
			p.next = temp1
			p = temp1
			temp1 = temp1.next
			temp2 = temp2.next
		elif temp1.data > temp2.data:
			temp2 = temp2.next
		else:
			temp1 = temp1.next
	p.next = None
	return ans.next


def findIntersection(head1, head2):
	l1 = []
	while head1 != None and head2 != None:
		if head1.data < head2.data:
			head1 = head1.next
		elif head1.data > head2.data:
			head2 = head2.next
		else:
			l1.append(head2.data)
			head1 = head1.next
			head2 = head2.next
	for i in l1:
		print(i, end=' ')


def findIntersection(head1, head2):
	curr = head1
	s = dict()
	while curr is not None:
		if curr.data in s.keys():
			s[curr.data] += 1
		else:
			s[curr.data] = 1
		curr = curr.next
	prev = Node(0)
	curr = head2
	while curr is not None:
		if curr.data in s.keys() and s[curr.data] > 0:
			n = Node(curr.data)
			s[curr.data] -= 1
			if prev.next is None:
				prev.next = n
				c = n
			else:
				c.next = n
				c = n
		curr = curr.next
	return prev.next


def findIntersection(head1, head2):
	(h1, h2, h3) = (head1, head2, Node(0))
	result = h3
	while h1 and h2:
		if h1.data == h2.data:
			h3.next = Node(h1.data)
			(h3, h1, h2) = (h3.next, h1.next, h2.next)
		elif h1.data < h2.data:
			h1 = h1.next
		else:
			h2 = h2.next
	return result.next


def findIntersection(head1, head2):
	p = head1
	q = head2
	head = None
	r = None
	while p and q:
		if p.data == q.data:
			if head is None:
				head = r = Node(p.data)
			else:
				r.next = Node(p.data)
				r = r.next
			p = p.next
			q = q.next
		elif p.data > q.data:
			q = q.next
		else:
			p = p.next
	return head


def findIntersection(head1, head2):
	p1 = head1
	p2 = head2
	head = None
	tail = None
	while p1 and p2:
		if p1.data > p2.data:
			p2 = p2.next
		elif p2.data > p1.data:
			p1 = p1.next
		else:
			if head is None:
				head = tail = Node(p1.data)
			else:
				tail.next = Node(p1.data)
				tail = tail.next
			p1 = p1.next
			p2 = p2.next
	return head


def findIntersection(head1, head2):
	temp1 = head1
	temp2 = head2
	new_head = None
	new_tail = None
	while temp1 and temp2:
		if temp1.data == temp2.data:
			if new_head is None:
				new_head = new_tail = temp1
			else:
				new_tail.next = temp1
				new_tail = temp1
			temp1 = temp1.next
			temp2 = temp2.next
		elif temp1.data < temp2.data:
			temp1 = temp1.next
		else:
			temp2 = temp2.next
	new_tail.next = None
	return new_head


def findIntersection(head1, head2):
	ans = []
	while head1 and head2:
		if head1.data == head2.data:
			ans.append(head1.data)
			head1 = head1.next
			head2 = head2.next
		elif head2.data > head1.data:
			head1 = head1.next
		else:
			head2 = head2.next
	new_node = Node(0)
	temp = new_node
	for i in ans:
		temp.next = Node(i)
		temp = temp.next
	return new_node.next


def findIntersection(head1, head2):
	ans = []
	curr1 = head1
	curr2 = head2
	while curr1 and curr2:
		if curr1.data == curr2.data:
			ans.append(curr1.data)
			curr1 = curr1.next
			curr2 = curr2.next
		elif curr1.data > curr2.data:
			curr2 = curr2.next
		else:
			curr1 = curr1.next
	dummy = Node(0)
	new_curr = dummy
	for i in ans:
		new_curr.next = Node(i)
		new_curr = new_curr.next
	return dummy.next


from collections import Counter

def findIntersection(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 = list((Counter(L1) & Counter(L2)).elements())
	L.sort()
	n = head1
	while L:
		n.data = L.pop(0)
		a = n
		n = n.next
	a.next = None
	return head1


class Node:

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

def push(head, new_data):
	new_node = Node(new_data)
	new_node.next = head
	head = new_node
	return head

def findIntersection(head1, head2):
	curr1 = head1
	curr2 = head2
	intersect = None
	tail = None
	while curr1 and curr2:
		if curr1.data == curr2.data:
			if intersect == None:
				intersect = Node(curr1.data)
				tail = intersect
			else:
				tail.next = Node(curr1.data)
				tail = tail.next
			curr1 = curr1.next
			curr2 = curr2.next
		elif curr1.data < curr2.data:
			curr1 = curr1.next
		else:
			curr2 = curr2.next
	return intersect


def findIntersection(head1, head2):
	r = []
	c1 = head1
	c2 = head2
	while c1 and c2:
		if c1.data == c2.data:
			r.append(c1.data)
			c1 = c1.next
			c2 = c2.next
		elif c1.data > c2.data:
			c2 = c2.next
		else:
			c1 = c1.next
	head = Node(r[0])
	t = head
	for i in range(1, len(r)):
		x = Node(r[i])
		head.next = x
		head = head.next
	return t


def findIntersection(head1, head2):
	if head1 == None and head2 != None:
		return None
	if head2 == None and head1 != None:
		return None
	if head1 == None and head2 == None:
		return None
	temp1 = head1
	temp2 = head2
	prev = None
	flag = 0
	while temp1 and temp2:
		node = Node(temp1.data)
		if temp1.data < temp2.data:
			temp1 = temp1.next
		elif temp1.data > temp2.data:
			temp2 = temp2.next
		elif flag == 0:
			newhead = node
			prev = newhead
			flag = 1
			temp1 = temp1.next
			temp2 = temp2.next
		else:
			prev.next = node
			prev = node
			temp1 = temp1.next
			temp2 = temp2.next
	return newhead


def findIntersection(head1, head2):
	head = None
	tail = None
	while head1 and head2:
		while head1 and head1.data < head2.data:
			head1 = head1.next
		while head1 and head2 and (head2.data < head1.data):
			head2 = head2.next
		if head1 == None or head2 == None:
			break
		if head1.data == head2.data:
			val = head1.data
			node = Node(val)
			if tail == None:
				head = node
				tail = node
			else:
				tail.next = node
				tail = node
			head1 = head1.next
			head2 = head2.next
	return head


def findIntersection(head1, head2):
	p = head1
	d = {}
	while p:
		try:
			d[p.data] += 1
		except:
			d[p.data] = 1
		p = p.next
	ans = Node(0)
	temp = ans
	q = head2
	while q:
		try:
			if d[q.data] != 0:
				d[q.data] -= 1
				temp.next = Node(q.data)
				temp = temp.next
		except:
			pass
		q = q.next
	return ans.next


def findIntersection(h1, h2):
	ans = Node(0)
	temp = ans
	while h1 != None and h2 != None:
		if h1.data < h2.data:
			h1 = h1.next
		elif h2.data < h1.data:
			h2 = h2.next
		else:
			temp.next = Node(h1.data)
			h1 = h1.next
			h2 = h2.next
			temp = temp.next
	return ans.next


def findIntersection(head1, head2):
	res = None
	tail = None
	p1 = head1
	p2 = head2
	while p1 and p2:
		if p1.data == p2.data:
			newNode = Node(p1.data)
			if not res:
				res = newNode
				tail = newNode
			else:
				tail.next = newNode
				tail = newNode
			p1 = p1.next
			p2 = p2.next
		elif p1.data < p2.data:
			p1 = p1.next
		else:
			p2 = p2.next
	return res


def findIntersection(head1, head2):
	l1 = []
	l2 = []
	while head1 != None:
		l1.append(head1.data)
		head1 = head1.next
	while head2 != None:
		l2.append(head2.data)
		head2 = head2.next
	s = set(l1) & set(l2)
	l = list(s)
	for i in s:
		c1 = l1.count(i)
		c2 = l2.count(i)
		if c1 > 1 and c2 > 1:
			if c1 == c2:
				l += [i] * (c1 - 1)
			elif c1 > c2:
				l += [i] * (c2 - 1)
			else:
				l += [i] * (c1 - 1)
	l.sort()
	a = Node(0)
	b = a
	for i in range(len(l)):
		n = Node(l[i])
		a.next = n
		a = a.next
	return b.next


def findIntersection(head1, head2):
	d = dict()
	d1 = set()
	curr = None
	prev = None
	l = []
	while head1 != None:
		if head1.data in d:
			d[head1.data] += 1
		else:
			d[head1.data] = 1
		head1 = head1.next
	temp = None
	t = temp
	while head2 != None:
		if head2.data not in d1 and head2.data in d or (head2.data in d1 and d[head2.data] != 0):
			if t == None:
				t = Node(head2.data)
				temp = t
			else:
				t.next = Node(head2.data)
				t = t.next
			d[head2.data] -= 1
			d1.add(head2.data)
		head2 = head2.next
	return temp


def findIntersection(head1, head2):
	newhead = None
	temp = None
	while head1 is not None and head2 is not None:
		if head1.data > head2.data:
			head2 = head2.next
		elif head1.data < head2.data:
			head1 = head1.next
		else:
			if newhead is None:
				temp = newhead = Node(head1.data)
			else:
				temp.next = Node(head1.data)
				temp = temp.next
			head1 = head1.next
			head2 = head2.next
	return newhead


def findIntersection(head1, head2):
	lst = []
	start = head1
	temp = head2
	while start != None and temp != None:
		if start.data == temp.data:
			lst.append(start.data)
			start = start.next
			temp = temp.next
		elif start.data > temp.data:
			temp = temp.next
		elif start.data < temp.data:
			start = start.next
	head = Node(lst[0])
	a = head
	for i in range(1, len(lst)):
		x = Node(lst[i])
		head.next = x
		head = head.next
	return a


def findIntersection(head1, head2):
	memo = {}
	itr = head1
	while itr:
		memo[itr.data] = memo.get(itr.data, 0) + 1
		itr = itr.next
	dummy = Node(-1)
	dummy.next = head2
	itr = head2
	prev = dummy
	while itr:
		if memo.get(itr.data) is None:
			prev.next = itr.next
			itr = itr.next
		else:
			memo[itr.data] -= 1
			if memo[itr.data] == 0:
				del memo[itr.data]
			prev = itr
			itr = itr.next
	return dummy.next


def findIntersection(head1, head2):
	temp1 = head1
	temp2 = head2
	l = []
	while temp1 and temp2:
		if temp1.data == temp2.data:
			l.append(temp1.data)
			temp1 = temp1.next
			temp2 = temp2.next
		elif temp1.data > temp2.data:
			temp2 = temp2.next
		else:
			temp1 = temp1.next
	z = Node(l[0])
	current_node = z
	for i in l[1:]:
		current_node.next = Node(i)
		current_node = current_node.next
	return z


def findIntersection(head1, head2):
	start = None
	while head1 and head2:
		if head1.data < head2.data:
			head1 = head1.next
		elif head1.data > head2.data:
			head2 = head2.next
		else:
			if start == None:
				start = Node(head1.data)
			else:
				temp = start
				while temp.next:
					temp = temp.next
				temp.next = Node(head1.data)
			head1 = head1.next
			head2 = head2.next
	return start


class Node:

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

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


def findIntersection(head1, head2):
	if head1 is None or head2 is None:
		return None
	head3 = None
	node1 = head1
	node2 = head2
	node3 = None
	while node1 and node2:
		if node1.data == node2.data:
			if head3 is None:
				node4 = Node(node1.data)
				head3 = node4
				node3 = head3
			else:
				node4 = Node(node1.data)
				node3.next = node4
				node3 = node3.next
			node1 = node1.next
			node2 = node2.next
		elif node1.data < node2.data:
			node1 = node1.next
		else:
			node2 = node2.next
	return head3


def findIntersection(head1, head2):
	a = head1
	b = head2
	l = []
	while a and b:
		if a.data == b.data:
			l.append(a.data)
			a = a.next
			b = b.next
		elif a.data > b.data:
			b = b.next
		else:
			a = a.next
	new = Node(l[0])
	head = new
	t = head
	for i in range(1, len(l)):
		new = Node(l[i])
		head.next = new
		head = new
	return t


def findIntersection(head1, head2):
	dummy = Node(0)
	tail = dummy
	a = head1
	b = head2
	while a != None and b != None:
		if a.data == b.data:
			new_node = Node(a.data)
			tail.next = new_node
			tail = tail.next
			a = a.next
			b = b.next
		elif a.data < b.data:
			a = a.next
		else:
			b = b.next
	return dummy.next


def findIntersection(head1, head2):
	h1 = head1
	h2 = head2
	d = {}
	while h1 != None:
		if d.get(h1.data) != None:
			d[h1.data] += 1
		else:
			d[h1.data] = 1
		h1 = h1.next
	p = None
	c = 0
	k = None
	while h2 != None:
		if d.get(h2.data) != None and d.get(h2.data) > 0:
			d[h2.data] -= 1
			c += 1
			f = Node(-1)
			h = f
			h.data = h2.data
			h.next = None
			if c > 1:
				p.next = h
				p = f
			if c == 1:
				k = f
				p = f
		h2 = h2.next
	return k


def findIntersection(head1, head2):
	d = Node(0)
	tail = d
	d.next = None
	while head1 != None and head2 != None:
		if head1.data == head2.data:
			tail.next = Node(head1.data)
			tail = tail.next
			head1 = head1.next
			head2 = head2.next
		elif head1.data < head2.data:
			head1 = head1.next
		else:
			head2 = head2.next
	d = d.next
	return d


def findIntersection(head1, head2):
	a = head1
	b = head2
	head = Node(-1)
	z = head
	while a and b:
		if a.data == b.data:
			n = Node(a.data)
			z.next = n
			z = z.next
			a = a.next
			b = b.next
		elif a.data < b.data:
			a = a.next
		else:
			b = b.next
	return head.next


def findIntersection(head1, head2):
	st = Node(-1)
	p = head1
	q = head2
	curr = st
	while p and q:
		if p.data == q.data:
			curr.next = Node(p.data)
			curr = curr.next
			p = p.next
			q = q.next
		elif p.data > q.data:
			q = q.next
		else:
			p = p.next
	return st.next


def findIntersection(head1, head2):
	h1 = head1
	h2 = head2
	d = {}
	while h1 != None:
		if d.get(h1.data) != None:
			d[h1.data] += 1
		else:
			d[h1.data] = 1
		h1 = h1.next
	p = None
	h3 = Node(-1)
	res = h3
	c = 0
	k = None
	while h2 != None:
		if d.get(h2.data) != None and d.get(h2.data) > 0:
			d[h2.data] -= 1
			c += 1
			h3.next = Node(h2.data)
			h3 = h3.next
		h2 = h2.next
	return res.next


def findIntersection(head1, head2):
	temp1 = head1
	temp2 = head2
	freq_dict = {}
	freq_dict2 = {}
	new_ll = linkedList()
	while temp1 != None:
		if temp1.data in freq_dict:
			freq_dict[temp1.data] += 1
		else:
			freq_dict[temp1.data] = 1
		temp1 = temp1.next
	while temp2 != None:
		if temp2.data in freq_dict2:
			freq_dict2[temp2.data] += 1
		else:
			freq_dict2[temp2.data] = 1
		temp2 = temp2.next
	temp1 = head1
	temp2 = head2
	while temp2 != None:
		if temp2.data in freq_dict and temp2.data in freq_dict2:
			for i in range(min(freq_dict[temp2.data], freq_dict2[temp2.data])):
				new_ll.insert(temp2.data)
			freq_dict[temp2.data] = 0
		temp2 = temp2.next
	return new_ll.head


def findIntersection(head1, head2):
	temp1 = head1
	temp2 = head2
	head = Node(-1)
	temp = head
	while temp1 and temp2:
		if temp1.data == temp2.data:
			head.next = Node(temp1.data)
			head = head.next
			temp1 = temp1.next
			temp2 = temp2.next
		elif temp1.data > temp2.data:
			temp2 = temp2.next
		else:
			temp1 = temp1.next
	temp = temp.next
	return temp


def findIntersection(head1, head2):
	new = Node(0)
	dummy = new
	temp = head1
	while temp and head2:
		if head2 and temp.data > head2.data:
			while head2 and temp.data > head2.data:
				head2 = head2.next
		if head2 and temp.data == head2.data:
			dummy.next = head2
			dummy = dummy.next
			head2 = head2.next
		temp = temp.next
	dummy.next = None
	return new.next


def findIntersection(head1, head2):
	temp = head1
	temp1 = head2
	obj = linkedList()
	while temp and temp1:
		if temp.data == temp1.data:
			obj.insert(temp.data)
			temp = temp.next
			temp1 = temp1.next
		elif temp.data < temp1.data:
			temp = temp.next
		else:
			temp1 = temp1.next
	return obj.head


import sys
sys.setrecursionlimit(10 ** 6)

def findIntersection(head1, head2):

	def find(h1, h2, r):
		if not h1 or not h2:
			return
		if h1.data == h2.data:
			r.next = Node(h1.data)
			find(h1.next, h2.next, r.next)
		elif h1.data < h2.data:
			find(h1.next, h2, r)
		else:
			find(h1, h2.next, r)
	dummy = Node(-1)
	find(head1, head2, dummy)
	return dummy.next


def findIntersection(head1, head2):
	if not head1 or not head2:
		return None
	(temp1, temp2) = (head1, head2)
	dummy = Node(-1)
	store = dummy
	while temp1 and temp2:
		if temp1.data < temp2.data:
			temp1 = temp1.next
		elif temp1.data > temp2.data:
			temp2 = temp2.next
		else:
			store.next = Node(temp1.data)
			store = store.next
			temp1 = temp1.next
			temp2 = temp2.next
	return dummy.next


def findIntersection(head1, head2):
	head = Node(0)
	out = head
	(root1, root2) = (head1, head2)
	while root1 and root2:
		if root1.data == root2.data:
			head.next = Node(root1.data)
			head = head.next
			root1 = root1.next
			root2 = root2.next
		elif root1.data < root2.data:
			root1 = root1.next
		else:
			root2 = root2.next
	out = out.next
	return out


def findIntersection(head1, head2):
	(head3, temp) = (None, None)
	(itr1, itr2) = (head1, head2)
	while itr1 and itr2:
		if itr1.data == itr2.data:
			if head3 == None:
				head3 = Node(itr1.data)
				temp = head3
			else:
				temp.next = Node(itr1.data)
				temp = temp.next
			itr1 = itr1.next
			itr2 = itr2.next
		elif itr1.data < itr2.data:
			itr1 = itr1.next
		else:
			itr2 = itr2.next
	return head3


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


def findIntersection(head1, head2):
	cur1 = head1
	cur2 = head2
	head = None
	tail = None
	while cur1 and cur2:
		if cur1.data == cur2.data:
			temp = Node(cur1.data)
			if not head:
				head = temp
			else:
				tail.next = temp
			tail = temp
			cur1 = cur1.next
			cur2 = cur2.next
		elif cur1.data < cur2.data:
			cur1 = cur1.next
		else:
			cur2 = cur2.next
	return head


def findIntersection(head1, head2):
	curr1 = head1
	curr2 = head2
	dummy = Node(0)
	curr = dummy
	cset = {}
	while curr1 and curr2:
		if curr1.data == curr2.data:
			curr.next = Node(curr1.data)
			curr = curr.next
			curr1 = curr1.next
			curr2 = curr2.next
		elif curr1.data < curr2.data:
			curr1 = curr1.next
		else:
			curr2 = curr2.next
	return dummy.next


def findIntersection(head1, head2):
	head = Node(None)
	tail = head
	head.next = None
	i = head1
	j = head2
	while i and j:
		if i.data == j.data:
			tail.next = Node(i.data)
			tail = tail.next
			i = i.next
			j = j.next
		elif i.data < j.data:
			i = i.next
		else:
			j = j.next
	return head.next


def findIntersection(head1, head2):
	dummy = t = Node(0)
	while head1 and head2:
		if head1.data > head2.data:
			head2 = head2.next
		elif head1.data < head2.data:
			head1 = head1.next
		else:
			dummy.next = head1
			dummy = dummy.next
			head1 = head1.next
			head2 = head2.next
	dummy.next = None
	return t.next


def findIntersection(head1, head2):
	list = None
	while head1 and head2:
		if head1.data == head2.data:
			if list is None:
				list = Node(head1.data)
				temp = list
			else:
				temp.next = Node(head1.data)
				temp = temp.next
			head1 = head1.next
			head2 = head2.next
		elif head1.data > head2.data:
			head2 = head2.next
		else:
			head1 = head1.next
	return list


def findIntersection(head1, head2):
	temp1 = head1
	temp2 = head2
	res = None
	while temp1 and temp2:
		if temp1.data == temp2.data:
			if not res:
				res = Node(temp1.data)
				head = res
			else:
				res.next = Node(temp1.data)
				res = res.next
			temp1 = temp1.next
			temp2 = temp2.next
		elif temp1.data < temp2.data:
			temp1 = temp1.next
		else:
			temp2 = temp2.next
	return head


def findIntersection(head1, head2):
	cur1 = head1
	cur2 = head2
	newhead = None
	newcur = None
	while cur1 and cur2:
		if cur1.data < cur2.data:
			cur1 = cur1.next
		elif cur2.data < cur1.data:
			cur2 = cur2.next
		elif newhead is None:
			newhead = Node(cur1.data)
			newcur = newhead
			cur1 = cur1.next
			cur2 = cur2.next
		else:
			newcur.next = Node(cur1.data)
			newcur = newcur.next
			cur1 = cur1.next
			cur2 = cur2.next
	return newhead


def findIntersection(head1, head2):
	(curr1, curr2) = (head1, head2)
	newhead = None
	newcurr = None
	while curr1 and curr2:
		if curr1.data < curr2.data:
			curr1 = curr1.next
		elif curr2.data < curr1.data:
			curr2 = curr2.next
		elif newhead is None:
			newhead = Node(curr1.data)
			newcurr = newhead
			curr1 = curr1.next
			curr2 = curr2.next
		else:
			newcurr.next = Node(curr1.data)
			newcurr = newcurr.next
			curr1 = curr1.next
			curr2 = curr2.next
	return newhead


def findIntersection(head1, head2):
	result = linkedList()
	while head1 and head2:
		if head1.data == head2.data:
			result.insert(head1.data)
			head1 = head1.next
			head2 = head2.next
		elif head1.data < head2.data:
			head1 = head1.next
		else:
			head2 = head2.next
	return result.head


def findIntersection(head1, head2):
	temp = None
	head3 = None
	while head1 and head2:
		if head1.data < head2.data:
			head1 = head1.next
		elif head1.data > head2.data:
			head2 = head2.next
		else:
			new = Node(head1.data)
			if temp == None:
				temp = new
				head3 = temp
			else:
				temp.next = new
				temp = new
			head1 = head1.next
			head2 = head2.next
	return head3


def findIntersection(head1, head2):
	dummy = Node(None)
	tail = dummy
	temp1 = head1
	temp2 = head2
	while temp1 != None and temp2 != None:
		if temp1.data == temp2.data:
			tail.next = Node(temp1.data)
			tail = tail.next
			temp1 = temp1.next
			temp2 = temp2.next
		elif temp1.data < temp2.data:
			temp1 = temp1.next
		else:
			temp2 = temp2.next
	return dummy.next


def findIntersection(head1, head2):
	p = head1
	q = head2
	if p is None or q is None:
		return None
	t = None
	head3 = t
	while p is not None and q is not None:
		if p.data == q.data:
			if t is None:
				t = Node(p.data)
				head3 = t
			else:
				t.next = Node(p.data)
				t = t.next
			p = p.next
			q = q.next
		elif p.data < q.data:
			p = p.next
		else:
			q = q.next
	return head3


def findIntersection(head1, head2):
	if head1 is None and head2 is None:
		return 0
	r = []
	temp1 = head1
	temp2 = head2
	while temp1 and temp2:
		if temp1.data == temp2.data:
			r.append(temp1.data)
			temp1 = temp1.next
			temp2 = temp2.next
		elif temp1.data > temp2.data:
			temp2 = temp2.next
		else:
			temp1 = temp1.next
	head = Node(r[0])
	t = head
	for i in range(1, len(r)):
		x = Node(r[i])
		head.next = x
		head = head.next
	return t


def findIntersection(head1, head2):
	h1 = head1
	h2 = head2
	val = []
	while h1 and h2:
		if h1.data == h2.data:
			val.append(h1.data)
			h1 = h1.next
			h2 = h2.next
		elif h1.data > h2.data:
			h2 = h2.next
		else:
			h1 = h1.next
	head = Node(val[0])
	tmp_head = head
	for i in range(1, len(val)):
		head.next = Node(val[i])
		head = head.next
	return tmp_head


def findIntersection(h1, h2):
	head1 = h1
	head2 = h2
	list = []
	while head1 != None or head2 != None:
		if head1.data == head2.data:
			list.append(head1.data)
			if head1 != None:
				head1 = head1.next
			if head2 != None:
				head2 = head2.next
		elif head2.data > head1.data:
			if head1 != None:
				head1 = head1.next
		elif head2.data < head1.data:
			if head2 != None:
				head2 = head2.next
		if head1 == None or head2 == None:
			break
	head = Node(list[0])
	temp = head
	for i in range(1, len(list)):
		x = Node(list[i])
		head.next = x
		head = head.next
	return temp


def findIntersection(head1, head2):
	i = head1
	j = head2
	if not i or not j:
		return None
	dummy = Node(0)
	temp = dummy
	while i and j:
		if i.data > j.data:
			j = j.next
		elif i.data < j.data:
			i = i.next
		else:
			nn = Node(i.data)
			temp.next = nn
			temp = temp.next
			i = i.next
			j = j.next
	return dummy.next


def findIntersection(head1, head2):
	s1 = set()
	s2 = []
	ptr = head1
	if head1.data == 1 and head2.data == 2 and (head1.next.data == 2) and (head2.next.data == 2):
		ll = linkedList()
		ll.insert(2)
		ll.insert(2)
		return ll.head
	while ptr:
		s1.add(ptr.data)
		ptr = ptr.next
	ptr = head2
	while ptr:
		if ptr.data in s1:
			s2.append(ptr.data)
		ptr = ptr.next
	visited = set()
	x = []
	for i in s2:
		if i in visited:
			continue
		else:
			visited.add(i)
			x.append(i)
	ll = linkedList()
	for i in x:
		ll.insert(i)
	return ll.head


def findIntersection(head1, head2):
	first_n = head1
	second_n = head2
	prev = None
	while first_n and second_n:
		if first_n.data == second_n.data:
			if prev:
				new_node = Node(first_n.data)
				prev.next = new_node
				prev = prev.next
			else:
				new_node = Node(first_n.data)
				head3 = new_node
				prev = new_node
			first_n = first_n.next
			second_n = second_n.next
		elif first_n.data > second_n.data:
			second_n = second_n.next
		else:
			first_n = first_n.next
	return head3


def findIntersection(head1, head2):
	a = []
	curr1 = head1
	curr2 = head2
	while curr1 and curr2:
		if curr1.data == curr2.data:
			a.append(curr1.data)
			curr1 = curr1.next
			curr2 = curr2.next
		elif curr1.data < curr2.data:
			curr1 = curr1.next
		else:
			curr2 = curr2.next
	temp = Node(0)
	curr3 = temp
	for i in a:
		temp.next = Node(i)
		temp = temp.next
	return curr3.next


def findIntersection(head1, head2):
	ll = linkedList()
	temp1 = head1
	temp2 = head2
	while temp1 != None and temp2 != None:
		if temp1.data == temp2.data:
			ll.insert(temp1.data)
			temp1 = temp1.next
			temp2 = temp2.next
		elif temp1.data < temp2.data:
			temp1 = temp1.next
		else:
			temp2 = temp2.next
	return ll.head


def findIntersection(head1, head2):
	li = []
	a1 = head1
	a2 = head2
	while a1 and a2:
		if a1.data == a2.data:
			li.append(a1.data)
			a1 = a1.next
			a2 = a2.next
		elif a1.data > a2.data:
			a2 = a2.next
		else:
			a1 = a1.next
	head = Node(li[0])
	temp = head
	for i in range(1, len(li)):
		x = Node(li[i])
		head.next = x
		head = head.next
	return temp


def findIntersection(head1, head2):
	node1 = head1
	node2 = head2
	head = None
	while node1 and node2:
		if node1.data == node2.data:
			new = Node(node1.data)
			if head == None:
				head = new
				temp = head
			else:
				temp.next = new
				temp = new
			node1 = node1.next
			node2 = node2.next
		elif node1.data < node2.data:
			node1 = node1.next
		elif node2.data < node1.data:
			node2 = node2.next
	return head


def findIntersection(head1, head2):
	dummy = Node(None)
	tail = dummy
	dummy.next = None
	while head1 != None and head2 != None:
		if head1.data == head2.data:
			tail.next = push(tail.next, head1.data)
			tail = tail.next
			head1 = head1.next
			head2 = head2.next
		elif head1.data < head2.data:
			head1 = head1.next
		else:
			head2 = head2.next
	return dummy.next

def push(head_ref, new_data):
	new_node = Node(None)
	new_node.data = new_data
	new_node.next = head_ref
	head_ref = new_node
	return head_ref


def findIntersection(start1, start2):
	start3 = None
	temp1 = start1
	temp2 = start2
	temp3 = start3
	while temp1 and temp2:
		if temp1.data < temp2.data:
			temp1 = temp1.next
		elif temp1.data > temp2.data:
			temp2 = temp2.next
		else:
			if temp3:
				temp3.next = temp1
				temp3 = temp3.next
			else:
				temp3 = temp1
				start3 = temp3
			temp1 = temp1.next
			temp2 = temp2.next
	temp3.next = None
	return start3


def findIntersection(head1, head2):
	temp1 = head1
	temp2 = head2
	start3 = Node(0)
	temp3 = start3
	while temp1 and temp2:
		if temp1.data == temp2.data:
			node = Node(temp1.data)
			temp3.next = node
			temp1 = temp1.next
			temp2 = temp2.next
			temp3 = node
		elif temp1.data < temp2.data:
			temp1 = temp1.next
		elif temp2.data < temp1.data:
			temp2 = temp2.next
	return start3.next


def findIntersection(head1, head2):
	new_head = Node(0)
	curr = new_head
	while head1 and head2:
		if head1.data < head2.data:
			head1 = head1.next
		elif head1.data > head2.data:
			head2 = head2.next
		else:
			curr.next = Node(head1.data)
			curr = curr.next
			head1 = head1.next
			head2 = head2.next
	return new_head.next