Given two singly linked lists of size N and M, write a program to get the point where two linked lists intersect each other.
 
Example 1:
Input:
LinkList1 = 3->6->9->common
LinkList2 = 10->common
common = 15->30->NULL
Output: 15
Explanation:
Example 2:
Input: 
Linked List 1 = 4->1->common
Linked List 2 = 5->6->1->common
common = 8->4->5->NULL
Output: 8
Explanation: 
4              5
|              |
1              6
 \             /
  8   -----  1 
   |
   4
   |
  5
  |
  NULL       
Your Task:
You don't need to read input or print anything. The task is to complete the function intersetPoint() which takes the pointer to the head of linklist1(head1) and linklist2(head2) as input parameters and returns data value of a node where two linked lists intersect. If linked list do not merge at any point, then it should return -1.
Challenge : Try to solve the problem without using any extra space.
 
Expected Time Complexity: O(N+M)
Expected Auxiliary Space: O(1)
 
Constraints:
1 ≤ N + M ≤ 2*10^{5}
-1000 ≤ value ≤ 1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3

'''

	Function to return the value at point of intersection

	in two linked list, connected in y shaped form.

	

	Function Arguments: head_a, head_b (heads of both the lists)

	

	Return Type: value in NODE present at the point of intersection

	             or -1 if no common point.



	Contributed By: Nagendra Jha



	{

		# Node Class

		class Node:

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

		        self.data = data

		        self.next = None

	}

'''



#Function to find intersection point in Y shaped Linked Lists.

class Solution:

    

    def intersetPoint(self,head1,head2):

        #code here

Solutions:
class Solution:

	def intersetPoint(self, h1, head2):
		s = set([])
		while h1 != None:
			h1 = h1.next
			s.add(h1)
		while head2 != None:
			if head2 in s:
				return head2.data
			head2 = head2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		h1 = head1
		h2 = head2
		l1 = 0
		l2 = 0
		while h2 != None:
			l2 += 1
			h2 = h2.next
		while h1 != None:
			l1 += 1
			h1 = h1.next
		if l1 > l2:
			for i in range(l1 - l2):
				head1 = head1.next
		else:
			for i in range(l2 - l1):
				head2 = head2.next
		while head1 != head2:
			head1 = head1.next
			head2 = head2.next
		if head1 == None or head2 == None:
			return -1
		return head1.data


class Solution:

	def intersetPoint(self, head1, head2):
		d1 = 0
		c1 = head1
		while c1:
			d1 += 1
			c1 = c1.next
		d2 = 0
		c2 = head2
		while c2:
			d2 += 1
			c2 = c2.next
		while d1 > d2:
			d1 -= 1
			head1 = head1.next
		while d2 > d1:
			d2 -= 1
			head2 = head2.next
		while head1 and head2:
			if head1 == head2:
				return head1.data
			head1 = head1.next
			head2 = head2.next
		return -1
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		temp1 = head1
		c1 = 0
		while temp1 != None:
			temp1 = temp1.next
			c1 += 1
		temp2 = head2
		c2 = 0
		while temp2 != None:
			temp2 = temp2.next
			c2 += 1
		temp1 = head1
		temp2 = head2
		if c1 > c2:
			n = c1 - c2
			for i in range(n):
				temp1 = temp1.next
			while temp1 != temp2:
				temp1 = temp1.next
				temp2 = temp2.next
			return temp1.data
		else:
			n = c2 - c1
			for i in range(n):
				temp2 = temp2.next
			while temp1 != temp2:
				temp1 = temp1.next
				temp2 = temp2.next
			return temp1.data


class Solution:

	def intersetPoint(self, head1, head2):
		data1 = 0
		data2 = 0
		temp1 = head1
		temp2 = head2
		while temp1 != None:
			data1 = data1 + 1
			temp1 = temp1.next
		while temp2 != None:
			data2 = data2 + 1
			temp2 = temp2.next
		if data1 == data2:
			temp1 = head1
			temp2 = head2
			while temp1 != temp2:
				temp1 = temp1.next
				temp2 = temp2.next
			if temp1 == None:
				return -1
			else:
				return temp1.data
		elif data1 > data2:
			excess = data1 - data2
			temp1 = head1
			temp2 = head2
			for i in range(excess):
				temp1 = temp1.next
			return Solution.intersetPoint(self, temp1, temp2)
		else:
			excess = data2 - data1
			temp1 = head1
			temp2 = head2
			for i in range(excess):
				temp2 = temp2.next
			return Solution.intersetPoint(self, temp1, temp2)


class Solution:

	def intersetPoint(self, head1, head2):

		def ll_len(node):
			length = 0
			while node:
				length += 1
				node = node.next
			return length
		len1 = ll_len(head1)
		len2 = ll_len(head2)
		if len1 > len2:
			(len1, len2, head1, head2) = (len2, len1, head2, head1)
		(node1, node2) = (head1, head2)
		for _ in range(len2 - len1):
			node2 = node2.next
		while node1 != node2:
			node1 = node1.next
			node2 = node2.next
		if node1 is None:
			return -1
		else:
			return node1.data


class Solution:

	def intersetPoint(self, head1, head2):
		cur1 = head1
		cur2 = head2
		while cur1 and cur2:
			if cur1 == cur2:
				return cur1.data
			if cur1.data > 1000:
				return cur1.data - 1001
			elif cur2.data > 1000:
				return cur2.data - 1001
			elif cur1.data < -1000:
				return cur1.data + 1001
			elif cur2.data < -1000:
				return cur2.data + 1001
			if cur1.data >= 0:
				cur1.data = cur1.data + 1001
			else:
				cur1.data = cur1.data - 1001
			if cur2.data >= 0:
				cur2.data = cur2.data + 1001
			else:
				cur2.data = cur2.data - 1001
			cur1 = cur1.next
			cur2 = cur2.next
		while cur1:
			if cur1.data > 1000:
				return cur1.data - 1001
			elif cur1.data < -1000:
				return cur1.data + 1001
			cur1 = cur1.next
		while cur2:
			if cur2.data > 1000:
				return cur2.data - 1001
			elif cur2.data < -1000:
				return cur2.data + 1001
			cur2 = cur2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		n = self.l(head1)
		m = self.l(head2)
		t1 = head1.next
		t2 = head2.next
		while t1 != None or t2 != None:
			if n > m:
				t1 = t1.next
				n -= 1
			elif n < m:
				t2 = t2.next
				m -= 1
			else:
				if t2 == t1:
					return t1.data
				t2 = t2.next
				t1 = t1.next
		return -1

	def l(self, temp):
		n = 0
		while temp != None:
			temp = temp.next
			n += 1
		return n


class Solution:

	def intersetPoint(self, head1, head2):
		special = Node(None)
		cur = head1
		while cur is not None:
			nxt = cur.next
			cur.next = special
			cur = nxt
		cur = head2
		nxt = head2.next
		while nxt is not None:
			if nxt.data is None:
				return cur.data
			cur = nxt
			nxt = cur.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		m = dict()
		c1 = head1
		c2 = head2
		while c1:
			m[c1] = 'visited'
			c1 = c1.next
		while c2:
			if c2 in m.keys():
				return c2.data
			c2 = c2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		d = set()
		while head1:
			d.add(head1)
			head1 = head1.next
		while head2:
			if head2 in d:
				return head2.data
			head2 = head2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		p1 = head1
		p2 = head2
		t1 = 10 ** 3
		t2 = 10 ** 4
		while p1 and p2:
			if p1 != p2:
				if p1.data > t1:
					return p1.data - t2
				if p2.data > t1:
					return p2.data - t2
				p1.data += t2
				p2.data += t2
			else:
				return p1.data
			p1 = p1.next
			p2 = p2.next
		while p1:
			if p1.data > t1:
				return p1.data - t2
			p1 = p1.next
		while p2:
			if p2.data > t1:
				return p2.data - t2
			p2 = p2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		l1 = head1
		l2 = head2
		while l1 != l2:
			l1 = l1.next if l1 else head2
			l2 = l2.next if l2 else head1
		return l1.data if l1 else -1


class Solution:

	def intersetPoint(self, head1, head2):
		t1 = head1
		t2 = head2
		c1 = c2 = 0
		while t1:
			c1 += 1
			t1 = t1.next
		while t2:
			c2 += 1
			t2 = t2.next
		dif = abs(c1 - c2)
		if c2 > c1:
			(head1, head2) = (head2, head1)
			(c1, c2) = (c2, c1)
		while dif:
			head1 = head1.next
			dif -= 1
		while head1 and head2 and (head1 != head2):
			head1 = head1.next
			head2 = head2.next
		if not head1:
			return -1
		return head1.data


class Solution:

	def intersetPoint(self, head1, head2):
		curr1 = head1
		curr2 = head2
		m = self.getLength(head1)
		n = self.getLength(head2)
		diff = m - n
		smaller = None
		bigger = None
		if diff < 0:
			smaller = head1
			bigger = head2
		elif diff > 0:
			smaller = head2
			bigger = head1
		else:
			return self.traverseTogetherTillMeet(head1, head2)
		newBigger = self.moveAheadByUnits(bigger, abs(diff))
		return self.traverseTogetherTillMeet(smaller, newBigger)

	def moveAheadByUnits(self, head, units):
		curr = head
		count = 0
		while curr and count < units:
			curr = curr.next
			count += 1
		return curr

	def traverseTogetherTillMeet(self, head1, head2):
		curr1 = head1
		curr2 = head2
		while curr1 and curr2:
			if id(curr1) == id(curr2):
				return curr1.data
			curr1 = curr1.next
			curr2 = curr2.next
		return None

	def getLength(self, head):
		length = 0
		curr = head
		while curr:
			length += 1
			curr = curr.next
		return length


class Solution:

	def intersetPoint(self, head1, head2):
		(ct1, ct2) = (0, 0)
		(temp1, temp2) = (head1, head2)
		while temp1:
			ct1 += 1
			temp1 = temp1.next
		while temp2:
			ct2 += 1
			temp2 = temp2.next
		(temp1, temp2) = (head1, head2)
		if ct1 > ct2:
			d = ct1 - ct2
			while d > 0:
				temp1 = temp1.next
				d -= 1
		if ct2 > ct1:
			d = ct2 - ct1
			while d > 0:
				temp2 = temp2.next
				d -= 1
		while temp1 and temp2 and (temp1 != temp2):
			(temp1, temp2) = (temp1.next, temp2.next)
		if temp1 is None:
			return -1
		return temp1.data


class Solution:

	def intersetPoint(self, head1, head2):
		n = 0
		tmp = head1
		while tmp:
			n += 1
			tmp = tmp.next
		m = 0
		tmp = head2
		while tmp:
			m += 1
			tmp = tmp.next
		if m > n:
			tmp1 = head2
			tmp2 = head1
		else:
			tmp1 = head1
			tmp2 = head2
		d = abs(m - n)
		while d > 0:
			d -= 1
			tmp1 = tmp1.next
		while tmp1 and tmp2:
			if tmp1 == tmp2:
				return tmp1.data
			tmp1 = tmp1.next
			tmp2 = tmp2.next


class Solution:

	def intersetPoint(self, head1, head2):
		dummy1 = head1
		dummy2 = head2
		while dummy1 and dummy2:
			if dummy1 == dummy2:
				return dummy1.data
			dummy1 = dummy1.next
			dummy2 = dummy2.next
		if not dummy1 and (not dummy2):
			return -1
		count = 0
		if dummy1:
			longer = head1
			shorter = head2
			while dummy1:
				count += 1
				dummy1 = dummy1.next
		elif dummy2:
			longer = head2
			shorter = head1
			while dummy2:
				count += 1
				dummy2 = dummy2.next
		for _ in range(count):
			longer = longer.next
		while longer and shorter:
			if longer == shorter:
				return longer.data
			longer = longer.next
			shorter = shorter.next
		return -1
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		x = set()
		while head1:
			x.add(head1)
			head1 = head1.next
		while head2:
			if head2 in x:
				return head2.data
			head2 = head2.next


class Solution:

	def intersetPoint(self, head1, head2):
		c1 = 0
		c2 = 0
		a = head1
		while a:
			c1 += 1
			a = a.next
		a = head2
		while a:
			c2 += 1
			a = a.next
		if c1 > c2:
			a = head1
			b = head2
		elif c1 < c2:
			a = head2
			b = head1
		else:
			a = head1
			b = head2
		d = abs(c1 - c2)
		i = 0
		while i < d:
			a = a.next
			i += 1
		while a and b and (a != b):
			a = a.next
			b = b.next
		if a == None:
			return -1
		return a.data


def getSize(head):
	ret = 0
	while head is not None:
		head = head.next
		ret += 1
	return ret

class Solution:

	def intersetPoint(self, head1, head2):
		n1 = getSize(head1)
		n2 = getSize(head2)
		while n1 > n2:
			head1 = head1.next
			n1 -= 1
		while n2 > n1:
			head2 = head2.next
			n2 -= 1
		while head1 != head2:
			head1 = head1.next
			head2 = head2.next
		if head1 is not None:
			return head1.data
		return -1


class Solution:

	def getLength(self, head):
		cnt = 0
		while head:
			cnt += 1
			head = head.next
		return cnt

	def getIntersectionPoint(self, d, head1, head2):
		c1 = head1
		c2 = head2
		for i in range(d):
			if c1 is None:
				return -1
			c1 = c1.next
		while c1 is not None and c2 is not None:
			if c1 == c2:
				return c1.data
			c1 = c1.next
			c2 = c2.next
		return -1

	def intersetPoint(self, head1, head2):
		c1 = self.getLength(head1)
		c2 = self.getLength(head2)
		if c1 > c2:
			d = c1 - c2
			return self.getIntersectionPoint(d, head1, head2)
		else:
			d = c2 - c1
			return self.getIntersectionPoint(d, head2, head1)


class Solution:

	def intersetPoint(self, head1, head2):
		tmp_dict = dict()
		while head1 is not None:
			if head1 not in tmp_dict:
				tmp_dict[head1] = 1
			head1 = head1.next
		while head2 is not None:
			if head2 not in tmp_dict:
				tmp_dict[head2] = 1
			else:
				return head2.data
			head2 = head2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		tmp_head = head1
		head1_size = 0
		head2_size = 0
		while tmp_head is not None:
			head1_size += 1
			tmp_head = tmp_head.next
		tmp_head = head2
		while tmp_head is not None:
			head2_size += 1
			tmp_head = tmp_head.next
		if head1_size > head2_size:
			for _ in range(head1_size - head2_size):
				head1 = head1.next
		elif head1_size < head2_size:
			for _ in range(head2_size - head1_size):
				head2 = head2.next
		while head1 != head2:
			head1 = head1.next
			head2 = head2.next
		return head1.data


class Solution:

	def linkLength(self, head):
		length = 0
		temp = head
		while temp != None:
			length += 1
			temp = temp.next
		return length

	def detect(self, head1, head2):
		temp1 = head1
		temp2 = head2
		while temp1 and temp2:
			if temp1 == temp2:
				return temp1.data
			temp1 = temp1.next
			temp2 = temp2.next
		return -1

	def intersetPoint(self, head1, head2):
		N = self.linkLength(head1)
		M = self.linkLength(head2)
		if N > M:
			times = N - M
			temp = head1
			while times > 0:
				temp = temp.next
				times -= 1
			return self.detect(temp, head2)
		elif M > N:
			times = M - N
			temp = head2
			while times > 0:
				temp = temp.next
				times -= 1
			return self.detect(head1, temp)
		else:
			return self.detect(head1, head2)


class Solution:

	def intersetPoint(self, head1, head2):
		if head1 is None or head2 is None:
			return -1

		def lengthOfList(head):
			count = 0
			current = head
			while current:
				count += 1
				current = current.next
			return count
		lengthHead1 = lengthOfList(head1)
		lengthHead2 = lengthOfList(head2)
		current_head1 = head1
		current_head2 = head2
		if lengthHead1 > lengthHead2:
			for i in range(lengthHead1 - lengthHead2):
				current_head1 = current_head1.next
		if lengthHead2 > lengthHead1:
			for i in range(lengthHead2 - lengthHead1):
				current_head2 = current_head2.next
		while current_head2 is not None and current_head1 is not None:
			if current_head1 == current_head2:
				return current_head1.data
			current_head1 = current_head1.next
			current_head2 = current_head2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		a = set()
		while head1 != None:
			a.add(head1)
			head1 = head1.next
		while head2 != None:
			if head2 in a:
				return head2.data
			else:
				a.add(head2)
				head2 = head2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		len1 = 0
		curr1 = head1
		while curr1:
			len1 += 1
			curr1 = curr1.next
		len2 = 0
		curr2 = head2
		while curr2:
			len2 += 1
			curr2 = curr2.next
		diff = abs(len1 - len2)
		if len1 < len2:
			(head1, head2) = (head2, head1)
		curr = head1
		i = 0
		while curr and i < diff:
			i += 1
			curr = curr.next
		curr2 = head2
		while curr and curr2:
			if curr == curr2:
				return curr.data
			curr = curr.next
			curr2 = curr2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		c1 = head1
		c11 = head1
		count1 = 0
		count2 = 0
		c2 = head2
		c22 = head2
		while c1 is not None:
			c1 = c1.next
			count1 = count1 + 1
		while c2 is not None:
			c2 = c2.next
			count2 = count2 + 1
		if count1 - count2 == 0:
			while c22 != c11:
				c22 = c22.next
				c11 = c11.next
			if c22 is None:
				return -1
			else:
				return c22.data
		else:
			a = abs(count1 - count2)
			if count1 > count2:
				k = 0
				while k != a:
					c11 = c11.next
					k = k + 1
				while c11 != c22:
					c11 = c11.next
					c22 = c22.next
				if c22 is None:
					return -1
				else:
					return c22.data
			else:
				k = 0
				while k != a:
					c22 = c22.next
					k = k + 1
				while c11 != c22:
					c11 = c11.next
					c22 = c22.next
				if c22 is None:
					return -1
				else:
					return c22.data


class Solution:

	def intersetPoint(self, head1, head2):
		(temp1, temp2) = (head1, head2)
		(len1, len2) = (0, 0)
		while temp1 != None:
			len1 += 1
			temp1 = temp1.next
		while temp2 != None:
			len2 += 1
			temp2 = temp2.next
		length = abs(len1 - len2)
		if len1 > len2:
			while length > 0:
				head1 = head1.next
				length -= 1
		else:
			while length > 0:
				head2 = head2.next
				length -= 1
		flag = True
		value = -1
		while flag == True and head1 != None:
			if head1 == head2:
				value = head1.data
				flag = False
			head1 = head1.next
			head2 = head2.next
		return value


def findlen(head):
	curr = head
	l = 0
	while curr:
		l += 1
		curr = curr.next
	return l

class Solution:

	def intersetPoint(self, head1, head2):
		len1 = findlen(head1)
		len2 = findlen(head2)
		if len1 > len2:
			for i in range(len1 - len2):
				head1 = head1.next
		elif len1 < len2:
			for i in range(len2 - len1):
				head2 = head2.next
		while head1 and head2:
			if head1 == head2:
				return head1.data
			head1 = head1.next
			head2 = head2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		l1 = 0
		l2 = 0
		curr1 = head1
		curr2 = head2
		while curr1:
			l1 += 1
			curr1 = curr1.next
		while curr2:
			l2 += 1
			curr2 = curr2.next
		if l1 > l2:
			while head1 and l1 != l2:
				head1 = head1.next
				l1 -= 1
		else:
			while head2 and l2 != l1:
				head2 = head2.next
				l2 -= 1
		while head1 and head2 and (head1 != head2):
			head1 = head1.next
			head2 = head2.next
		if head1 != head2:
			return -1
		return head2.data


class Solution:

	def intersetPoint(self, head1, head2):
		tek1 = head1
		n1 = 0
		while tek1 != None:
			n1 += 1
			tek1 = tek1.next
		tek2 = head2
		n2 = 0
		while tek2 != None:
			n2 += 1
			tek2 = tek2.next
		if n1 == n2:
			tek1 = head1
			tek2 = head2
		elif n1 > n2:
			k = n1 - n2
			tek1 = head1
			tek2 = head2
			i = 0
			while i < k:
				tek1 = tek1.next
				i += 1
		else:
			k = n2 - n1
			tek1 = head1
			tek2 = head2
			i = 0
			while i < k:
				tek2 = tek2.next
				i += 1
		while tek1 != None and tek2 != None:
			if tek1 == tek2:
				return tek1.data
			tek1 = tek1.next
			tek2 = tek2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		t1 = head1
		t2 = head2
		a = set()
		b = set()
		while t1 != None:
			a.add(t1)
			t1 = t1.next
		while t2 != None:
			if t2 in a:
				return t2.data
			t2 = t2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		t1 = head1
		t2 = head2
		a = set()
		b = set()
		while t1 != None:
			a.add(t1)
			t1 = t1.next
		while t2 != None:
			if t2 in a:
				return t2.data
			b.add(t2)
			t2 = t2.next
		c = tuple(a.intersection(b))
		if c == 0:
			return -1
		t3 = head1
		while t3 != c:
			t3 = t3.next
		return t3.data


class Solution:

	def intersetPoint(self, head1, head2):
		i1 = 0
		head = head1
		while head:
			head = head.next
			i1 += 1
		i2 = 0
		head = head2
		while head:
			head = head.next
			i2 += 1
		n1 = max(0, i1 - i2)
		n2 = max(0, i2 - i1)
		for _ in range(n1):
			head1 = head1.next
		for _ in range(n2):
			head2 = head2.next
		while head1 and head2:
			if head1 == head2:
				return head1.data
			head1 = head1.next
			head2 = head2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		setti = set()
		while head1:
			setti.add(head1)
			head1 = head1.next
		while head2 and head2.next not in setti:
			head2 = head2.next
		return head2.next.data if head2.next else -1


class Solution:

	def intersetPoint(self, head1, head2):
		count1 = 0
		count2 = 0
		node1 = head1
		node2 = head2
		while node1:
			count1 += 1
			node1 = node1.next
		while node2:
			count2 += 1
			node2 = node2.next
		if count1 > count2:
			diff = count1 - count2
			node1 = head1
			node2 = head2
			while diff > 0:
				diff -= 1
				node1 = node1.next
			while node1:
				if node1 == node2:
					return node1.data
				node1 = node1.next
				node2 = node2.next
		else:
			diff = count2 - count1
			node1 = head1
			node2 = head2
			while diff > 0:
				diff -= 1
				node2 = node2.next
			while node1:
				if node1 == node2:
					return node1.data
				node1 = node1.next
				node2 = node2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		ptr1 = head1
		ptr2 = head2
		while ptr1 != ptr2:
			if ptr1 is None:
				ptr1 = head2
			if ptr2 is None:
				ptr2 = head1
			ptr1 = ptr1.next
			ptr2 = ptr2.next
		return ptr1.data


class Solution:

	def intersetPoint(self, head1, head2):
		p1 = head1
		p2 = head2
		while p1 != p2:
			p1 = p1.next
			p2 = p2.next
			if p1 == p2:
				return p1.data
			if p1 == None:
				p1 = head2
			if p2 == None:
				p2 = head1
		return p2.data


class Solution:

	def intersetPoint(self, head1, head2):

		def getLen(head):
			n = 0
			cur = head
			while cur:
				cur = cur.next
				n += 1
			return n
		(n, m) = (getLen(head1), getLen(head2))
		if n <= m:
			i = m - n
			while i > 0:
				head2 = head2.next
				i -= 1
		else:
			i = n - m
			while i > 0:
				head1 = head1.next
				i -= 1
		while head1 and head2:
			if head1 == head2:
				return head1.data
			head1 = head1.next
			head2 = head2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		if head1 and head2:
			(cur1, cur2) = (head1, head2)
		if not head1 or not head2:
			return -1
		while cur1 != cur2:
			if cur1:
				cur1 = cur1.next
			else:
				cur1 = head2
			if cur2:
				cur2 = cur2.next
			else:
				cur2 = head1
		return cur1.data if cur1 else -1


class Solution:

	def intersetPoint(self, head1, head2):
		(cur1, cur2) = (head1, head2)
		(travel1, travel2) = (False, False)
		while not travel1 or not travel2:
			cur1 = cur1.next
			cur2 = cur2.next
			if cur1 == None:
				cur1 = head2
				travel1 = True
			if cur2 == None:
				cur2 = head1
				travel2 = True
		while cur1 != None:
			if cur1 == cur2:
				return cur1.data
			cur1 = cur1.next
			cur2 = cur2.next
		return -1


class Solution:

	def intersetPoint(self, headA, headB):
		(lenA, lenB) = (0, 0)
		(currA, currB) = (headA, headB)
		while currA:
			lenA += 1
			currA = currA.next
		while currB:
			lenB += 1
			currB = currB.next
		(currA, currB) = (headA, headB)
		if lenA > lenB:
			for i in range(lenA - lenB):
				currA = currA.next
		else:
			for i in range(lenB - lenA):
				currB = currB.next
		while currA != currB:
			currA = currA.next
			currB = currB.next
		return currA.data


class Solution:

	def intersetPoint(self, head1, head2):
		if not head1 or not head2:
			return -1
		l1 = head1
		l2 = head2
		while l1 != l2:
			l1 = l1.next if l1 else head2
			l2 = l2.next if l2 else head1
		if not l1:
			return -1


class Solution:

	def intersetPoint(self, head1, head2):
		ptr1 = head1
		ptr2 = head2
		while ptr1 != ptr2:
			if ptr1 == None:
				ptr1 = head2
			if ptr2 == None:
				ptr2 = head1
			ptr1 = ptr1.next
			ptr2 = ptr2.next
		if not ptr1:
			return -1
		return ptr1.data


class Solution:

	def intersetPoint(self, head1, head2):
		d1 = {}
		d2 = {}
		h1 = head1
		h2 = head2
		if h1 is None or h2 is None:
			return -1
		while h1 or h2:
			if h1:
				d1[h1] = True
				if d2.get(h1) is True:
					return h1.data
				h1 = h1.next
			if h2:
				d2[h2] = True
				if d1.get(h2) is True:
					return h2.data
				h2 = h2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		v1 = []
		v2 = []
		while head1 != None:
			v1.append(head1.next)
			head1 = head1.next
		flag = -1
		while head2 != None:
			v2.append(head2.next)
			head2 = head2.next
		cnt = 0
		(M, N) = (len(v1), len(v2))
		v1.reverse()
		v2.reverse()
		for (i, j) in zip(v1, v2):
			if i != j:
				break
			else:
				cnt += 1
		nxt = v1[cnt - 1]
		flag = nxt.data
		return flag


class Solution:

	def solve(self, count1, count2, head1, head2):
		diff = count1 - count2
		ptr1 = head1
		ptr2 = head2
		count = 0
		while ptr1 != None and ptr2 != None:
			if count < diff:
				ptr1 = ptr1.next
				count += 1
			else:
				if ptr1 == ptr2:
					return ptr1.data
				ptr1 = ptr1.next
				ptr2 = ptr2.next
		return -1

	def intersetPoint(self, head1, head2):
		arr1 = []
		arr2 = []
		ptr1 = head1
		ptr2 = head2
		count1 = 0
		count2 = 0
		while ptr1 != None:
			count1 += 1
			ptr1 = ptr1.next
		while ptr2 != None:
			count2 += 1
			ptr2 = ptr2.next
		if count1 > count2:
			return self.solve(count1, count2, head1, head2)
		else:
			return self.solve(count2, count1, head2, head1)


class Solution:

	def intersetPoint(self, head1, head2):
		d = {}
		temp = head1
		while temp:
			d[temp] = temp.data
			temp = temp.next
		temp = head2
		while temp:
			if temp in d:
				return d[temp]
			temp = temp.next
		return -1


class Solution:

	def get_list_length(self, head):
		length = 0
		while head is not None:
			length += 1
			head = head.next
		return length

	def go_to_index(self, head, index):
		for i in range(index):
			head = head.next
		return head

	def intersetPoint(self, head1, head2):
		length1 = self.get_list_length(head1)
		length2 = self.get_list_length(head2)
		min_length = min(length1, length2)
		head1 = self.go_to_index(head1, length1 - min_length)
		head2 = self.go_to_index(head2, length2 - min_length)
		while head1 is not None and head2 is not None:
			if head1 == head2:
				return head1.data
			head1 = head1.next
			head2 = head2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		p = head1
		q = head2
		c1 = 0
		c2 = 0
		while p:
			c1 = c1 + 1
			p = p.next
		while q:
			c2 = c2 + 1
			q = q.next
		p = head1
		q = head2
		diff = abs(c1 - c2)
		if c1 > c2:
			for i in range(diff):
				p = p.next
		if c2 > c1:
			for i in range(diff):
				q = q.next
		while p != q:
			p = p.next
			q = q.next
		if p:
			return p.data
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		a = head1
		b = head2
		while a != b:
			a = a.next if a else head2
			b = b.next if b else head1
		return a.data


class Solution:

	def intersetPoint(self, head1, head2):
		(p, q) = (head1, head2)
		c1 = 0
		c2 = 0
		ans = -1
		while p:
			c1 += 1
			p = p.next
		while q:
			c2 += 1
			q = q.next
		(p, q) = (head1, head2)
		di = abs(c1 - c2)
		if c1 > c2:
			while abs(c1 - c2) != 0:
				c1 -= 1
				p = p.next
		elif c1 < c2:
			while abs(c1 - c2) != 0:
				c2 -= 1
				q = q.next
		while p != q:
			p = p.next
			q = q.next
		if p.data != None:
			return p.data
		return -1


class Solution:

	def visit(self, head):
		if head:
			return self.visit(head.next) + 1
		return 0

	def intersetPoint(self, head1, head2):
		(l1, l2) = (0, 0)
		x = head1
		while x:
			x = x.next
			l1 += 1
		x = head2
		while x:
			x = x.next
			l2 += 1
		while l1 > l2:
			head1 = head1.next
			l1 -= 1
		while l2 > l1:
			head2 = head2.next
			l2 -= 1
		while head1 != head2:
			head1 = head1.next
			head2 = head2.next
		return head1.data


class Solution:

	def intersetPoint(self, head1, head2):
		if head1 == None or head2 == None:
			return -1
		(s, t) = (0, 0)
		p1 = head1
		while p1.next:
			s += 1
			p1 = p1.next
		p2 = head2
		while p2.next:
			t += 1
			p2 = p2.next
		if s > t:
			while s > t:
				head1 = head1.next
				s -= 1
		elif t > s:
			while t > s:
				head2 = head2.next
				t -= 1
		while head1 and head2:
			if head1 == head2:
				return head1.data
			head1 = head1.next
			head2 = head2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		if not head1 or not head2 or (not head1.next) or (not head2.next):
			return -1
		fast = head1
		slow = head2
		n = 0
		m = 0
		while fast:
			fast = fast.next
			n += 1
		while slow:
			slow = slow.next
			m += 1
		fast = head1
		slow = head2
		while n > m:
			n -= 1
			fast = fast.next
		while m > n:
			m -= 1
			slow = slow.next
		while fast and slow:
			if fast == slow:
				return fast.data
			fast = fast.next
			slow = slow.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		if not head1 or not head2:
			return -1
		s1 = set([])
		s2 = set([])
		while head1 or head2:
			if head1:
				if head1 in s2:
					return head1.data
				s1.add(head1)
				head1 = head1.next
			if head2:
				if head2 in s1:
					return head2.data
				s2.add(head2)
				head2 = head2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		if head1 is None or head2 is None:
			return -1
		p = head1
		while p.next is not None:
			p = p.next
		p.next = head2
		slow = head1
		fast = head1
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				break
		if fast is None:
			return -1
		fast = head1
		while fast:
			slow = slow.next
			fast = fast.next
			if slow == fast:
				break
		return slow.data


class Solution:

	def intersetPoint(self, head1, head2):
		ref1 = head1
		ref2 = head2
		while ref1 != ref2:
			if ref1 == None:
				ref1 = head2
			if ref2 == None:
				ref2 = head1
			ref1 = ref1.next
			ref2 = ref2.next
		return ref1.data


class Solution:

	def intersetPoint(self, head1, head2):
		(t1, t2) = (head1, head2)
		s1 = s2 = 0
		while t1 or t2:
			if t1:
				s1 += 1
				t1 = t1.next
			if t2:
				s2 += 1
				t2 = t2.next
		if s1 < s2:
			(s2, s1, head2, head1) = (s1, s2, head1, head2)
		(t1, t2) = (head1, head2)
		for i in range(0, s1 - s2):
			t1 = t1.next
		while t1 and t2 and (t1 != t2):
			t1 = t1.next
			t2 = t2.next
		return -1 if not t1 else t1.data


class Solution:

	def intersetPoint(self, head1, head2):
		p1 = head1
		p2 = head2
		l1 = 0
		l2 = 0
		while p1 or p2:
			if p1:
				p1 = p1.next
				l1 += 1
			if p2:
				p2 = p2.next
				l2 += 1
		p1 = head1 if l1 > l2 else head2
		for _ in range(abs(l2 - l1)):
			p1 = p1.next
		p2 = head1 if l1 <= l2 else head2
		while p1 and p2:
			if p1 == p2:
				return p1.data
			p1 = p1.next
			p2 = p2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		p = head1
		while p:
			p.data = (-1 if p.data < 0 else 1) * (abs(p.data) + 1001)
			p = p.next
		p = head2
		while p:
			if abs(p.data) > 1000:
				return (-1 if p.data < 0 else 1) * (abs(p.data) - 1001)
			p = p.next
		return -1


class Solution:

	def lenLL(self, llist):
		count = 0
		while llist is not None:
			llist = llist.next
			count += 1
		return count

	def intersetPoint(self, head1, head2):
		if id(head1) == id(head2):
			return head1.data
		ch1 = self.lenLL(head1)
		ch2 = self.lenLL(head2)
		if ch1 > ch2:
			node_A = head1
			node_B = head2
		else:
			node_A = head2
			node_B = head1
		for y in range(abs(ch2 - ch1)):
			node_A = node_A.next
			if id(node_A) == id(node_B):
				return node_A.data
		while node_A is not None:
			node_A = node_A.next
			node_B = node_B.next
			if id(node_A) == id(node_B):
				return node_A.data
		return -1


class Solution:

	def intersetPoint(self, head1, head2):

		def length(head):
			leng = 0
			while head != None:
				head = head.next
				leng += 1
			return leng
		l1 = length(head1)
		l2 = length(head2)
		d = abs(l1 - l2)
		if l1 > l2:
			temp1 = head1
			temp2 = head2
		else:
			temp1 = head2
			temp2 = head1
		while d:
			temp1 = temp1.next
			d -= 1
		while temp1 != None and temp2 != None:
			if temp1 == temp2:
				return temp1.data
			temp1 = temp1.next
			temp2 = temp2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		temp1 = head1
		temp2 = head2
		f = 0
		while temp1 != temp2:
			temp1 = temp1.next
			temp2 = temp2.next
			if temp1 == None:
				if f == 2:
					return -1
				f += 1
				temp1 = head2
			if temp2 == None:
				if f == 2:
					return -1
				f += 1
				temp2 = head1
		return temp1.data


class Solution:

	def intersetPoint(self, head1, head2):
		length_1 = 0
		length_2 = 0
		temp = head1
		while temp:
			length_1 += 1
			temp = temp.next
		temp = head2
		while temp:
			length_2 += 1
			temp = temp.next
		ptr1 = head1
		ptr2 = head2
		if length_1 > length_2:
			diff = length_1 - length_2
			for i in range(diff):
				ptr1 = ptr1.next
		else:
			diff = length_2 - length_1
			for i in range(diff):
				ptr2 = ptr2.next
		while ptr1 != None and ptr2 != None:
			if ptr1 == ptr2:
				return ptr1.data
			ptr1 = ptr1.next
			ptr2 = ptr2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		node1 = self.listOne(head1)
		node2 = self.listTwo(head2)
		if node2:
			return node2.data
		return -1

	def listOne(self, node):
		while node is not None:
			node.prev = 'ab'
			node = node.next

	def listTwo(self, node):
		while node is not None:
			if hasattr(node, 'prev'):
				return node
			node = node.next


class Solution:

	def intersetPoint(self, head1, head2):
		n1 = head1
		n2 = head2
		(l1, l2) = (0, 0)
		while n1.next:
			l1 += 1
			n1 = n1.next
		while n2.next:
			l2 += 1
			n2 = n2.next
		n1 = head1
		n2 = head2
		diff = 0
		if l1 > l2:
			diff = l1 - l2
			while diff > 0:
				n1 = n1.next
				diff -= 1
		else:
			diff = l2 - l1
			while diff > 0:
				n2 = n2.next
				diff -= 1
		while n1 is not None and n2 is not None:
			if n1 == n2:
				return n1.data
			n1 = n1.next
			n2 = n2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		dic1 = []
		dic2 = set()
		while head1:
			dic1.append(head1)
			head1 = head1.next
		while head2:
			dic2.add(head2)
			head2 = head2.next
		for ele in dic1:
			if ele in dic2:
				return ele.data
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		ptr1 = head1
		ptr2 = head2
		cnt1 = 0
		cnt2 = 0
		while ptr1 is not None:
			cnt1 += 1
			ptr1 = ptr1.next
		while ptr2 is not None:
			cnt2 += 1
			ptr2 = ptr2.next
		if cnt1 > cnt2:
			while cnt1 != cnt2:
				head1 = head1.next
				cnt1 -= 1
		elif cnt1 < cnt2:
			while cnt2 != cnt1:
				head2 = head2.next
				cnt2 -= 1
		if cnt1 == cnt2:
			while head1 != head2:
				head1 = head1.next
				head2 = head2.next
			if head1 is not None:
				return head1.data
			else:
				return -1


class Solution:

	def intersetPoint(self, head1, head2):
		t1 = head1
		c1 = 0
		t2 = head2
		c2 = 0
		t3 = head1
		while t1 != None:
			t1 = t1.next
			c1 += 1
		while t2 != None:
			t2 = t2.next
			c2 += 1
		diff = abs(c1 - c2)
		if c2 > c1:
			while diff > 0:
				head2 = head2.next
				diff -= 1
		else:
			while diff > 0:
				head1 = head1.next
				diff -= 1
		while head1 != None or head2 != None:
			if head1 == head2:
				return head1.data
			head1 = head1.next
			head2 = head2.next
		return -1


class Solution:

	def intersetPoint(self, head1, head2):
		(pointer1, pointer2) = (0, 0)
		temp1 = head1
		temp2 = head2
		t1 = head1
		t2 = head2
		while temp1 != None:
			pointer1 += 1
			temp1 = temp1.next
		while temp2 != None:
			pointer2 += 1
			temp2 = temp2.next
		dif = abs(pointer2 - pointer1)
		if pointer1 > pointer2:
			for i in range(dif):
				t1 = t1.next
		else:
			for i in range(dif):
				t2 = t2.next
		while t1 != t2:
			t1 = t1.next
			t2 = t2.next
		return t1.data


from collections import defaultdict as maps

class Solution:

	def intersetPoint(self, head1, head2):
		d = maps(bool)
		temp = head1
		while temp:
			d[temp] = True
			temp = temp.next
		temp = head2
		while temp:
			if d[temp]:
				return temp.data
			temp = temp.next


class Solution:

	def intersetPoint(self, head1, head2):
		p = head1
		q = head2
		len1 = 0
		len2 = 0
		while p is not None:
			p = p.next
			len1 += 1
		while q is not None:
			q = q.next
			len2 += 1
		p = head1
		q = head2
		if len1 > len2:
			for i in range(0, len1 - len2):
				p = p.next
		elif len2 > len1:
			for i in range(0, len2 - len1):
				q = q.next
		while p is not None:
			if p == q:
				break
			p = p.next
			q = q.next
		if p is not None:
			return p.data
		else:
			return -1