Given a singly linked list of N nodes. Find the first node of the loop if the linked list has a loop. If a loop is present return the node data of the first node of the loop else return -1.
Example 1:
Input:
Output: 3
Explanation:
We can see that there exists a loop 
in the given linked list and the first
node of the loop is 3.
 
Example 2:
Input:
Output: -1
Explanation: No loop exists in the above
linked list.So the output is -1.
 
Your Task:
The task is to complete the function findFirstNode() which contains reference to the head as only argument. This function should return the value of the first node of the loop if the linked list contains a loop, else return -1.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{5}
1 <= Data on Node <= 10^{6} 
0 <= pos <= N

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Amortized analysis

Starter code: #User function Template for python3



""" Node Class

    class Node:

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

            self.data = data

            self.next = None

"""

class Solution:

    #Function to find first node if the linked list has a loop.

    def findFirstNode(self, head):

        #code here

Solutions:
class Solution:

	def findFirstNode(self, head):
		if not head and (not head.next):
			return -1
		hashMap = {}
		curr = head
		while curr:
			isExists = hashMap.get(curr, None)
			if isExists:
				return curr.data
			hashMap[curr] = 1
			curr = curr.next
		return -1


class Solution:

	def findFirstNode(self, head):
		Freq = {}
		total_nodes = 0
		pos = 0
		temp = head
		while temp != None:
			if temp not in Freq:
				pos += 1
				Freq[temp] = pos
				total_nodes += 1
			else:
				break
			temp = temp.next
		if temp != None:
			return temp.data
		else:
			return -1


class Solution:

	def findFirstNode(self, head):
		slow = head
		fast = head
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				slow = head
				while slow != fast:
					slow = slow.next
					fast = fast.next
				return slow.data
		return -1


class Solution:

	def findFirstNode(self, head):
		s = set()
		while head:
			if head in s:
				return head.data
			s.add(head)
			head = head.next
		return -1


class Solution:

	def findFirstNode(self, head):
		if head is None or head.next is None:
			return -1
		slow = head
		fast = head
		slow = slow.next
		fast = fast.next.next
		while fast and fast.next:
			if id(slow) == id(fast):
				break
			slow = slow.next
			fast = fast.next.next
		if fast is None or fast.next is None:
			return -1
		slow = head
		while id(slow) != id(fast):
			slow = slow.next
			fast = fast.next
		return slow.data


class Solution:

	def floyd_detect_loop(self, head):
		slow = head
		fast = head
		while slow is not None and fast is not None and (fast.next is not None):
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				return slow
		return None

	def findFirstNode(self, head):
		if head is None:
			return -1
		intersection = self.floyd_detect_loop(head)
		if intersection is None:
			return -1
		slow = head
		while slow != intersection:
			slow = slow.next
			intersection = intersection.next
		return slow.data


class Solution:

	def findFirstNode(self, head):
		slow = head
		fast = head
		hasLoop = False
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				hasLoop = True
				break
		if hasLoop:
			slow = head
			while slow != fast:
				fast = fast.next
				slow = slow.next
			return slow.data
		return -1


class Solution:

	def findFirstNode(self, head):
		slow = fast = head
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				break
		if not fast or not fast.next:
			return -1
		slow = head
		while slow != fast:
			slow = slow.next
			fast = fast.next
		return slow.data


class Solution:

	def findFirstNode(self, head):
		s = set()
		temp = head
		while temp:
			if temp not in s:
				s.add(temp)
			else:
				return temp.data
			temp = temp.next
		return -1


class Solution:

	def findFirstNode(self, start):
		slow = start
		fast = start.next
		while fast:
			slow = slow.next
			fast = fast.next
			if fast:
				fast = fast.next
			if slow == fast:
				break
		else:
			return -1
		slow = start
		while slow != fast.next:
			slow = slow.next
			fast = fast.next
		return slow.data


class Solution:

	def findFirstNode(self, start):
		slow = start
		fast = start.next
		while fast and fast != slow:
			slow = slow.next
			fast = fast.next
			if fast:
				fast = fast.next
		if fast is None:
			return -1
		slow = start
		while slow != fast.next:
			slow = slow.next
			fast = fast.next
		return slow.data


class Solution:

	def findFirstNode(self, head):
		if head is None:
			return -1
		if head.next is None:
			return -1
		visited_nodes = dict()
		curr = head
		while curr is not None:
			if curr.next in visited_nodes:
				return curr.next.data
			visited_nodes[curr] = 1
			curr = curr.next
		return -1


class Solution:

	def findFirstNode(self, head):
		s = set()
		if head == None:
			return
		next1 = head
		next2 = head
		while next1 and next2 and next2.next:
			s.add(next1)
			next1 = next1.next
			next2 = next2.next.next
			if next1 in s:
				return next1.data
		return -1


class Solution:

	def findFirstNode(self, head):
		p = head
		q = head
		while p != None:
			try:
				p = p.next.next
				q = q.next
				if p == q:
					break
			except:
				return -1
		if p == None:
			return -1
		else:
			p = head
			while p != q:
				p = p.next
				q = q.next
			return p.data


class Solution:

	def findFirstNode(self, head):

		def cycle(slow, fast):
			if slow:
				slow = slow.next
			length = 1
			while slow != fast:
				slow = slow.next
				length += 1
			return length
		slow = head
		fast = head
		flag = True
		l = 0
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				l = cycle(slow, fast)
				break
		if l == 0:
			return -1
		temp = head
		temp2 = head
		while l > 0:
			temp = temp.next
			l -= 1
		while temp2 != temp:
			temp = temp.next
			temp2 = temp2.next
		return temp.data


class Solution:

	def findFirstNode(self, head):
		slow = fast = head
		while fast or fast.next:
			slow = slow.next
			fast = fast.next.next
			if fast == slow:
				loop_node = fast
				break
			if fast == None:
				break
		if fast == None or fast.next == None:
			return -1
		temp = head
		while temp != loop_node:
			temp = temp.next
			loop_node = loop_node.next
		return temp.data


class Solution:

	def findFirstNode(self, head):
		slow = head
		fast = head
		while fast != None and fast != next:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				break
		else:
			return -1
		slow = head
		while slow != fast:
			slow = slow.next
			fast = fast.next
			if slow == fast:
				return slow.data
		return slow.data


class Solution:

	def findFirstNode(self, head):
		slow = head
		fast = head
		while True:
			slow = slow.next
			if not fast:
				return -1
				break
			fast = fast.next.next
			if slow == fast:
				break
		q = head
		if q != slow:
			while q != slow:
				q = q.next
				slow = slow.next
		return q.data


class Solution:

	def findFirstNode(self, head):

		def detect(head):
			slow = head
			fast = head
			p = head
			while fast != None and fast.next.next != None:
				slow = slow.next
				fast = fast.next.next
				if slow == fast:
					return slow
			return None
		start = head
		meet = detect(head)
		if meet == None:
			return -1
		while start != meet:
			temp = meet
			meet = meet.next
			start = start.next
		return start.data


class Solution:

	def getMeetingPoint(self, head):
		slow = head
		fast = head
		while fast != None and fast.next != None:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				return slow
		return False

	def findFirstNode(self, head):
		meeting_point = self.getMeetingPoint(head)
		if not meeting_point:
			return -1
		start = head
		while start != meeting_point:
			start = start.next
			meeting_point = meeting_point.next
		return start.data


class Solution:

	def findFirstNode(self, head):
		(turtle, hare) = (head, head)
		while True:
			if turtle.next:
				turtle = turtle.next
			else:
				return -1
			if hare.next and hare.next.next:
				hare = hare.next.next
			else:
				return -1
			if turtle is hare:
				break
		start = head
		while start is not turtle:
			start = start.next
			turtle = turtle.next
		return start.data


class Solution:

	def findFirstNode(self, head):
		slow = head
		fast = head
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				break
		if not fast or not fast.next:
			return -1
		count = 1
		curr = slow.next
		while curr != slow:
			count += 1
			curr = curr.next
		slow = head
		fast = head
		for i in range(count):
			fast = fast.next
		while slow != fast:
			slow = slow.next
			fast = fast.next
		return slow.data


class Solution:

	def findFirstNode(self, head):
		if head == None or head.next == None:
			return -1
		slow = head
		fast = head
		fast = fast.next.next
		last = slow
		slow = slow.next
		while fast != None and fast.next != None:
			if fast == slow:
				fast = head
				while fast.next != slow.next:
					fast = fast.next
					slow = slow.next
				if slow == head:
					return head.data
				return slow.next.data
			fast = fast.next.next
			last = slow
			slow = slow.next
		return -1


class Solution:

	def findFirstNode(self, head):
		if not head.next or not head.next.next:
			return -1
		slow = head
		fast = head
		temp = head
		count = 0
		while fast.next and fast.next.next:
			fast = fast.next.next
			slow = slow.next
			if fast == slow:
				while temp != slow:
					temp = temp.next
					slow = slow.next
				return slow.data
		return -1


class Solution:

	def findFirstNode(self, head):
		lo = head
		hi = head
		while lo != None and hi != None and (hi.next != None) and (hi.next.next != None):
			lo = lo.next
			hi = hi.next.next
			if lo == hi:
				break
		if lo != hi:
			return -1
		lo = head
		if lo == head and hi == head:
			return head.data
		while lo.next != hi.next:
			lo = lo.next
			hi = hi.next
		if lo.next == hi.next:
			return lo.next.data


class Solution:

	def findFirstNode(self, head):
		temp = head
		ar = []
		ar = set(ar)
		while temp != None:
			ar.add(temp)
			temp = temp.next
			if temp in ar:
				return temp.data
		return -1


class Solution:

	def findFirstNode(self, head):
		fast = head
		slow = head
		mp = {}
		ans = False
		while fast and fast.next:
			fast = fast.next.next
			slow = slow.next
			if slow == fast:
				ans = True
				break
		if not ans:
			return -1
		slow = head
		while slow != fast:
			fast = fast.next
			slow = slow.next
		return slow.data


class Solution:

	def findFirstNode(self, head):
		if head is None or head.next is None:
			return -1

		def detect_loop(head):
			(slow, fast) = (head, head)
			while fast and fast.next:
				slow = slow.next
				fast = fast.next.next
				if slow == fast:
					return fast
			return False
		fast = detect_loop(head)
		if not fast:
			return -1
		slow = head
		while fast != slow:
			slow = slow.next
			fast = fast.next
		return slow.data


class Solution:

	def findFirstNode(self, head):
		s = set()
		prev = None
		h = head
		while h != None:
			if h in s:
				return h.data
			s.add(h)
			h = h.next
		return -1


class Solution:

	def findFirstNode(self, head):
		slow = head
		fast = head
		entry = head
		first = 'yes'
		if head == None or head.next == None:
			return -1
		while fast != None:
			if fast.next == None:
				break
			if slow == fast and first != 'yes':
				if entry == slow:
					return entry.data
				while entry.next != slow.next:
					entry = entry.next
					slow = slow.next
				return slow.next.data
			else:
				first = 'no'
			slow = slow.next
			fast = fast.next.next
		return -1


class Solution:

	def findFirstNode(self, head):
		node = self.get_first_node(head)
		if node is None:
			return -1
		return node.data

	def get_first_node(self, head):
		if head.next is None:
			return head
		slow = head.next
		fast = head.next.next
		answer = False
		while slow is not None and fast is not None and (fast.next is not None):
			if slow == fast:
				answer = True
				break
			else:
				slow = slow.next
				fast = fast.next.next
		if answer is not True:
			return None
		if slow == head and fast == head:
			return head
		else:
			slow = head
			while True:
				if slow.next == fast.next:
					return slow.next
				else:
					slow = slow.next
					fast = fast.next


class Solution:

	def findFirstNode(self, head):
		slower = head
		faster = slower.next
		while slower != faster and faster:
			slower = slower.next
			if faster.next:
				faster = faster.next.next
			else:
				faster = faster.next
		if not faster:
			return -1
		faster = faster.next
		lenght = 1
		while faster != slower:
			faster = faster.next
			lenght += 1
		slower = head
		faster = head
		for i in range(0, lenght):
			faster = faster.next
		while faster != slower:
			faster = faster.next
			slower = slower.next
		return slower.data


class Solution:

	def findFirstNode(self, head):
		(f, s) = (head, head)
		while f and f.next:
			fl = 0
			f = f.next.next
			s = s.next
			if f == s:
				break
		s = head
		if f == None or f.next == None:
			return -1
		while s != f:
			f = f.next
			s = s.next
		return f.data


class Solution:

	def findFirstNode(self, head):
		tmp = head
		dic = {}
		while tmp:
			if tmp in dic:
				return tmp.data
			else:
				dic[tmp] = 1
			tmp = tmp.next
		return -1


class Solution:

	def findFirstNode(self, head):
		d = {}
		while head:
			if head not in d:
				d[head] = 1
			else:
				return head.data
			head = head.next
		return -1


class Solution:

	def findFirstNode(self, head):
		s1 = f1 = head
		s1 = s1.next
		f1 = f1.next.next
		while s1 != f1:
			if not f1.next.next:
				return -1
			s1 = s1.next
			f1 = f1.next.next
		s2 = head
		while s1 != s2:
			s1 = s1.next
			s2 = s2.next
		return s1.data


class Solution:

	def findFirstNode(self, head):
		t = head
		r = head
		while r and r.next:
			r = r.next.next
			t = t.next
			if t == r:
				break
		if r == None or r.next == None:
			return -1
		while head:
			if head == t:
				return t.data
			head = head.next
			t = t.next


class Solution:

	def findFirstNode(self, head):
		current = head
		s = {}
		while current:
			if current in s:
				return s[current]
			s.update({current: current.data})
			current = current.next
		return -1


class Solution:

	def findFirstNode(self, head):
		look = set()
		curr = head
		while curr:
			if curr in look:
				return curr.data
			look.add(curr)
			curr = curr.next
		return -1


class Solution:

	def findFirstNode(self, head):
		slow = head
		fast = head
		f = 0
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				f = 1
				break
		if f == 0:
			return -1
		slow = head
		while slow != fast:
			slow = slow.next
			fast = fast.next
		return slow.data


class Solution:

	def findloop(self, head):
		slow = head
		fast = head
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				return slow
		return 0

	def findstart(self, head, start):
		curr = head
		while curr != start:
			curr = curr.next
			start = start.next
		return curr

	def findFirstNode(self, head):
		p = self.findloop(head)
		if p == 0:
			return -1
		else:
			s = self.findstart(head, p)
			return s.data


class Solution:

	def findFirstNode(self, head):
		first = head
		second = head
		while second and second.next:
			first = first.next
			second = second.next.next
			if first == second:
				break
		if first != second:
			return -1
		second = head
		while first != second:
			first = first.next
			second = second.next
		return first.data