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.

def intersetPoint(head1,head2):

    #code here

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


def intersetPoint(head1, head2):

	def length(head):
		count = 0
		cur = head
		while cur is not None:
			cur = cur.next
			count += 1
		return count
	l1 = length(head1)
	l2 = length(head2)

	def travel(head, c):
		cur = head
		for i in range(c):
			cur = cur.next
		return cur
	if l1 > l2:
		head1 = travel(head1, l1 - l2)
	elif l1 < l2:
		head2 = travel(head2, l2 - l1)
	i = head1
	j = head2
	while i is not None and j is not None and (i != j):
		i = i.next
		j = j.next
	if i is None or j is None:
		return -1
	return i.data


def intersetPoint(head1, head2):
	curr = head1
	len1 = 0
	while curr:
		len1 += 1
		curr = curr.next
	curr = head2
	len2 = 0
	while curr:
		len2 += 1
		curr = curr.next
	if len1 > len2:
		diff = len1 - len2
		while diff:
			head1 = head1.next
			diff -= 1
	elif len2 > len1:
		diff = len2 - len1
		while diff:
			head2 = head2.next
			diff -= 1
	while head1 and head2:
		if head1 == head2:
			return head1.data
		head1 = head1.next
		head2 = head2.next
	return -1


def intersetPoint(head1, head2):
	sai = set()
	curr1 = head1
	while curr1 != None:
		sai.add(curr1)
		curr1 = curr1.next
	curr2 = head2
	while curr2 != None:
		if curr2 in sai:
			return curr2.data
		curr2 = curr2.next
	return -1


def intersetPoint(head1, head2):
	hs = set()
	n1 = head1
	n2 = head2
	while n1 != None:
		hs.add(n1)
		n1 = n1.next
	while n2 != None:
		if n2 in hs:
			return n2.data
		n2 = n2.next
	return -1


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


def intersetPoint(head1, head2):
	if head1 == None and head2 == None:
		return -1
	curr1 = head1
	curr2 = head2
	while curr1 != curr2:
		curr1 = curr1.next if curr1 else head2
		curr2 = curr2.next if curr2 else head1
	if not curr1:
		return -1
	return curr1.data


def intersetPoint(head1, head2):
	l1 = 0
	l2 = 0
	p1 = head1
	p2 = head2
	while head1:
		l1 += 1
		head1 = head1.next
	while head2:
		l2 += 1
		head2 = head2.next
	head1 = p1
	head2 = p2
	d = abs(l1 - l2)
	if l1 > l2:
		while d > 0 and head1:
			head1 = head1.next
			d -= 1
		while head1 and head2:
			if head1 == head2:
				return head1.data
			head1 = head1.next
			head2 = head2.next
	else:
		while d > 0 and head2:
			head2 = head2.next
			d -= 1
		while head1 and head2:
			if head1 == head2:
				return head1.data
			head1 = head1.next
			head2 = head2.next
	return -1


def intersetPoint(headA, headB):
	(temp1, temp2) = (headA, headB)
	while temp1 and temp2:
		if temp1 == temp2:
			return temp1.data
		temp1 = temp1.next
		temp2 = temp2.next
	temp = temp1 or temp2
	c = 0
	while temp:
		c += 1
		temp = temp.next
	if temp1:
		temp = headA
	if temp2:
		temp = headB
	for i in range(c):
		temp = temp.next
	tempn = None
	if not temp1:
		tempn = headA
	elif not temp2:
		tempn = headB
	while tempn and temp:
		if tempn == temp:
			return temp.data
		tempn = tempn.next
		temp = temp.next
	return -1


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

def intersetPoint(head1, head2):
	len1 = getLength(head1)
	len2 = getLength(head2)
	diff = abs(len1 - len2)
	if len1 > len2:
		for i in range(diff):
			head1 = head1.next
	else:
		for i in range(diff):
			head2 = head2.next
	while head1 and head2:
		if head1 == head2:
			return head1.data
		head1 = head1.next
		head2 = head2.next
	return -1


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


def intersetPoint(head1, head2):
	front = head1
	c1 = 0
	while front is not None:
		c1 += 1
		front = front.next
	front = head2
	c2 = 0
	while front is not None:
		c2 += 1
		front = front.next
	front1 = head1
	front2 = head2
	if c1 > c2:
		d = c1 - c2
		while d > 0:
			front1 = front1.next
			d -= 1
	else:
		d = c2 - c1
		while d > 0:
			front2 = front2.next
			d -= 1
	while front1 is not None:
		if front1 == front2:
			return front1.data
		front1 = front1.next
		front2 = front2.next
	return -1


def intersetPoint(head1, head2):
	(itr1, itr2) = (head1, head2)
	(l1, l2) = (0, 0)
	while itr1:
		l1 += 1
		itr1 = itr1.next
	while itr2:
		l2 += 1
		itr2 = itr2.next
	(itr1, itr2) = (head1, head2)
	if l1 > l2:
		for i in range(l1 - l2):
			itr1 = itr1.next
	else:
		for i in range(l2 - l1):
			itr2 = itr2.next
	while itr1 and itr2:
		if itr1 == itr2:
			return itr1.data
		itr1 = itr1.next
		itr2 = itr2.next
	return -1


def intersetPoint(head1, head2):
	(curr1, curr2) = (head1, head2)
	(count1, count2) = (0, 0)
	while curr1:
		count1 += 1
		curr1 = curr1.next
	while curr2:
		count2 += 1
		curr2 = curr2.next
	a = head1
	b = head2
	if count1 > count2:
		for i in range(count1 - count2):
			a = a.next
	elif count2 > count1:
		for i in range(count2 - count1):
			b = b.next
	while a and b:
		if a == b:
			return a.data
		a = a.next
		b = b.next
	return -1


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


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


def intersetPoint(headA, headB):
	if headA == None or headB == None:
		return -1
	(a, b) = (headA, headB)
	while a != b:
		if a == None:
			a = headB
		else:
			a = a.next
		if b == None:
			b = headA
		else:
			b = b.next
	if a != None:
		return a.data
	else:
		return -1


class Node:

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

def getLength(head):
	count = 0
	while head:
		count += 1
		head = head.next
	return count

def intersetPoint(head1, head2):
	len1 = getLength(head1)
	len2 = getLength(head2)
	if len1 > len2:
		diff = len1 - len2
		while diff:
			head1 = head1.next
			diff -= 1
	else:
		diff = len2 - len1
		while diff:
			head2 = head2.next
			diff -= 1
	while head1 and head2:
		if head1 == head2:
			return head1.data
		head1 = head1.next
		head2 = head2.next
	return -1


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


def intersetPoint(head1, head2):
	if not head1 or not head2:
		return -1
	seen = set()
	temp = head1
	while temp:
		seen.add(temp)
		temp = temp.next
	temp2 = head2
	while temp2:
		if temp2 in seen:
			return temp2.data
		temp2 = temp2.next
	return -1


def intersetPoint(head1, head2):
	(count1, count2) = (0, 0)
	(temp1, temp2) = (head1, head2)
	while temp1:
		temp1 = temp1.next
		count1 += 1
	while temp2:
		temp2 = temp2.next
		count2 += 1
	(curr1, curr2) = (head1, head2)
	if count1 > count2:
		for i in range(abs(count1 - count2)):
			curr1 = curr1.next
	else:
		for i in range(abs(count1 - count2)):
			curr2 = curr2.next
	while curr1 and curr2:
		if curr1 == curr2:
			return curr1.data
		curr1 = curr1.next
		curr2 = curr2.next
	return -1


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


def intersetPoint(head1, head2):
	l1 = 0
	l2 = 0
	f1 = head1
	f2 = head2
	while f1 != None and f1.next != None:
		l1 += 2
		f1 = f1.next.next
	if f1 != None:
		l1 += 1
	while f2 != None and f2.next != None:
		l2 += 2
		f2 = f2.next.next
	if f2 != None:
		l2 += 1
	f1 = head1
	f2 = head2
	if l1 > l2:
		for i in range(l1 - l2):
			f1 = f1.next
	elif l2 > l1:
		for i in range(l2 - l1):
			f2 = f2.next
	while f1 != None and f2 != None:
		f1 = f1.next
		f2 = f2.next
		if f1 == f2 and f1 != None:
			return f1.data
	return -1


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

def intersetPoint(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


def intersetPoint(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