Given a linked list of size N. The task is to complete the function countNodesinLoop() that checks whether a given Linked List contains a loop or not and if the loop is present then return the count of nodes in a loop or else return 0. C is the position of the node to which the last node is connected. If it is 0 then no loop.
 
Example 1:
Input:
N = 10
value[]={25,14,19,33,10,21,39,90,58,45}
C = 4
Output: 7
Explanation: The loop is 45->33. So
length of loop is 33->10->21->39->
90->58->45 = 7. The number 33 is
connected to the last node to form the
loop because according to the input the
4^{th} node from the beginning(1 based
index) will be connected to the last
node for the loop.
Example 2:
Input:
N = 2
value[] = {1,0}
C = 1
Output: 2
Explanation: The length of the loop
is 2.
Your Task:
The task is to complete the function countNodesinLoop() which contains the only argument as reference to head of linked list and return the length of the loop ( 0 if there is no loop).
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 500
0 <= C <= N-1

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



'''

Structure of node



# Node Class

class Node:

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

        self.data = data

        self.next = None



'''



#Function to find the length of a loop in the linked list.

def countNodesinLoop(head):

    #Your code here

Solutions:
def countNodesinLoop(head):
	prev = head
	curr = head
	while prev and curr and curr.next:
		prev = prev.next
		curr = curr.next.next
		if prev == curr:
			c = 1
			prev = curr.next
			while prev != curr:
				prev = prev.next
				c += 1
			return c
	return 0


def countNodesinLoop(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 0
	req = fast.next
	result = 1
	while req != slow:
		req = req.next
		result += 1
	return result


def countNodesinLoop(head):
	slow = head
	fast = head
	while True:
		try:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				break
		except:
			return 0
	slow = slow.next
	l = 1
	while slow != fast:
		l += 1
		slow = slow.next
	return l


def countNodesinLoop(head):
	s = head
	f = head
	c = 0
	while f and f.next:
		s = s.next
		f = f.next.next
		if s == f:
			c = 1
			s = s.next
			while s != f:
				c += 1
				s = s.next
			return c
	return 0


def countNodesinLoop(head):
	fast = head
	slow = head
	c = 0
	while fast and fast.next:
		fast = fast.next.next
		slow = slow.next
		if slow == fast:
			c = 1
			slow = slow.next
			while slow != fast:
				c += 1
				slow = slow.next
			return c
	return 0


def countNodesinLoop(head):
	(s, f) = (head, head)
	c = False
	while f and f.next:
		(s, f) = (s.next, f.next.next)
		if s == f:
			c = True
			break
	if not c:
		return 0
	s = s.next
	c = 0
	while s != f:
		s = s.next
		c += 1
	return c + 1


def countNodesinLoop(head):
	(slow, fast) = (head, head)
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
		if slow == fast:
			break
	if fast == None or fast.next == None:
		return 0
	cnt = 1
	slow = slow.next
	while slow != fast:
		cnt += 1
		slow = slow.next
	return cnt


def countNodesinLoop(head):
	a = head
	b = head
	c = 0
	while b and b.next:
		a = a.next
		b = b.next.next
		if a == b:
			c = 1
			a = a.next
			while a != b:
				c += 1
				a = a.next
			return c
	return 0


def countNodesinLoop(head):
	slow = head
	fast = head
	flag = False
	while fast.next != None and fast.next.next != None:
		fast = fast.next.next
		slow = slow.next
		if slow == fast:
			flag = True
			break
	count = 0
	if flag == False:
		return 0
	slow = head
	while slow.next != fast.next:
		slow = slow.next
		fast = fast.next
	t = fast.next
	fast = t
	while fast.next != t:
		fast = fast.next
		count += 1
	return count + 1


def countNodesinLoop(head):
	(a, b) = (head, head)
	while b and b.next:
		a = a.next
		b = b.next.next
		if a == b:
			intersection = b
			a = head
			while a != intersection:
				a = a.next
				intersection = intersection.next
			start = a
			temp = start
			c = 1
			while temp.next != start:
				temp = temp.next
				c = c + 1
			return c
	return 0


def countNodesinLoop(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:
		pos = Freq[temp]
		return total_nodes - pos + 1
	else:
		return 0


def countNodesinLoop(head):
	if head is None:
		return 0
	(fast, slow) = (head, head)
	while fast and fast.next:
		fast = fast.next.next
		slow = slow.next
		if fast == slow:
			count = 1
			intersect = slow
			while intersect.next != slow:
				count += 1
				intersect = intersect.next
			return count
	return 0


def countNodesinLoop(head):
	slow = head
	fast = head
	if not head:
		return 0
	if head.next == head:
		return 1
	while slow and fast and slow.next and fast.next and fast.next.next:
		slow = slow.next
		fast = fast.next.next
		if slow == fast:
			length = 1
			slow = slow.next
			while fast != slow:
				length += 1
				slow = slow.next
			return length
	return 0


def countNodesinLoop(head):
	fast = slow = head
	while fast and fast.next:
		fast = fast.next.next
		slow = slow.next
		if fast == slow:
			break
	if not fast or not fast.next:
		return 0
	slow = head
	while fast != slow:
		fast = fast.next
		slow = slow.next
	count = 1
	while slow.next != fast:
		count += 1
		slow = slow.next
	return count


def countNodesinLoop(head):
	slow = head
	fast = head
	while fast != None and fast.next != None:
		slow = slow.next
		fast = fast.next.next
		if slow == fast:
			break
	else:
		return 0
	thirdpointer = head
	while thirdpointer != slow:
		thirdpointer = thirdpointer.next
		slow = slow.next
	fast = slow
	slow = slow.next
	counter = 1
	while slow != fast:
		slow = slow.next
		counter += 1
	return counter


def countNodesinLoop(head):
	count = 0
	mp = {}
	temp = head
	while temp:
		count += 1
		if mp.get(temp):
			return count - mp.get(temp)
		mp[temp] = count
		temp = temp.next
	return 0


def getlength(n):
	cnt = 1
	temp = n
	while temp.next != n:
		cnt += 1
		temp = temp.next
	return cnt

def countNodesinLoop(head):
	slow = head
	fast = head
	while slow and fast and (fast.next != None):
		slow = slow.next
		fast = fast.next.next
		if slow == fast:
			return getlength(slow)
	return 0


def countNodesinLoop(head):
	slow = head
	fast = head
	flag = 0
	ctr = 0
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
		if slow == fast:
			flag = 1
			break
	if flag == 0:
		return 0
	while slow:
		ctr += 1
		slow = slow.next
		if slow == fast:
			return ctr


def countNodesinLoop(head):
	(slow, fast) = (head, head)
	cycle = False
	while fast is not None and fast.next is not None:
		fast = fast.next.next
		slow = slow.next
		if id(slow) == id(fast):
			cycle = True
			break
	if cycle == False:
		return 0
	slow = head
	while True:
		if id(slow) == id(fast):
			break
		slow = slow.next
		fast = fast.next
	c = 1
	fast = fast.next
	while id(slow) != id(fast):
		c += 1
		fast = fast.next
	return c


def countNodesinLoop(head):
	slow = head
	fast = head
	extra = head
	while fast is not None and fast.next is not None:
		slow = slow.next
		fast = fast.next.next
		if slow == fast:
			while extra != slow:
				extra = extra.next
				slow = slow.next
			slow = slow.next
			index = 1
			while slow != extra:
				slow = slow.next
				index += 1
			return index
	return 0


def countNodesinLoop(head):
	slow = head
	fast = head
	count = 0
	while fast.next and fast.next.next:
		slow = slow.next
		count = count + 1
		fast = fast.next.next
		if fast == slow:
			break
	prev = slow
	c = 0
	a = 0
	if slow == fast:
		slow = head
		while slow != fast:
			slow = slow.next
			fast = fast.next
			a = a + 1
			c = c + 1
			if fast == prev and slow != fast:
				c = 0
		count = count + c - a
		return count
	return 0


def getstartnode(head):
	s = set()
	while head:
		if head in s:
			return head
		s.add(head)
		head = head.next
	return 0

def countNodesinLoop(head):
	l = getstartnode(head)
	p = 0
	t = l
	count = 0
	while l:
		count = count + 1
		if l.next == t:
			return count
		l = l.next
	return 0


def getstartnode(head):
	s = set()
	while head:
		if head in s:
			return head
		s.add(head)
		head = head.next
	return 0

def countNodesinLoop(head):
	c = getstartnode(head)
	if c == 0:
		return c
	else:
		res = 0
		temp = c
		while c:
			res = res + 1
			c = c.next
			if c == temp:
				return res


from collections import defaultdict

def countNodesinLoop(head):
	hashMap = set()
	temp = head
	while temp:
		if temp in hashMap:
			break
		hashMap.add(temp)
		temp = temp.next
	if temp is None:
		return 0
	hashMap = set()
	len = 0
	while temp:
		if temp in hashMap:
			break
		hashMap.add(temp)
		temp = temp.next
		len += 1
	return len


def countNodesinLoop(head):
	x = {}
	i = 0
	while head:
		if head in x:
			return len(x) - x[head]
		x[head] = i
		i = i + 1
		head = head.next
	return 0


def countNodesinLoop(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 0
	slow = start
	count = 1
	while slow != fast.next:
		slow = slow.next
		fast = fast.next
	temp = slow
	while fast != temp:
		temp = temp.next
		count += 1
	return count


def countNodesinLoop(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 0
	slow = start
	while slow != fast.next:
		slow = slow.next
		fast = fast.next
	ans = 1
	while slow != fast:
		slow = slow.next
		ans += 1
	return ans


def countNodesinLoop(head):
	slow = head
	fast = head
	loopstart = None
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
		if fast == slow:
			loopstart = slow
			break
	if not loopstart:
		return 0
	count = 1
	data = loopstart.next
	while data != loopstart:
		count += 1
		data = data.next
	return count


def countNodesinLoop(head):
	slow = head
	fast = head
	while fast != None and fast.next != None:
		slow = slow.next
		fast = fast.next.next
		if slow == fast:
			value = slow
			count = 1
			slow = slow.next
			while slow != value:
				count += 1
				slow = slow.next
			return count
	return 0


def countNodesinLoop(head):
	slow = head
	fast = head
	res = 0
	while fast != None:
		slow = slow.next
		if fast.next == None:
			return res
		fast = fast.next.next
		if slow == fast:
			slow = slow.next
			res += 1
			while slow != fast:
				slow = slow.next
				res += 1
			return res
	return res


def countNodesinLoop(head):
	fast = head.next
	slow = head
	while fast != slow:
		if fast is None or fast.next is None:
			return 0
		fast = fast.next.next
		slow = slow.next
	size = 1
	fast = fast.next
	while fast != slow:
		fast = fast.next
		size += 1
	return size


def countNodesinLoop(head):
	slow = head
	fast = head
	isloop = False
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
		if slow == fast:
			isloop = True
			break
	if isloop == False:
		return 0
	count = 1
	fast = fast.next
	while slow != fast:
		count += 1
		fast = fast.next
	return count


def countNodesinLoop(head):
	if head.next == None:
		return 0
	temp1 = head
	if head != None and head.next != None:
		temp2 = head.next
	count = 0
	ans = 0
	while temp1 != None and count != 2 and (temp2 != None):
		if temp1 == temp2:
			count += 1
		temp1 = temp1.next
		if temp2.next != None and temp2.next.next != None:
			temp2 = temp2.next.next
		else:
			temp2 = None
		if count == 1:
			ans += 1
	return ans


def countNodesinLoop(head):
	slow = fast = head
	while slow:
		slow = slow.next
		if fast and fast.next:
			fast = fast.next.next
		else:
			return 0
		if slow == fast:
			break
	fast = head
	while slow != fast:
		slow = slow.next
		fast = fast.next
	fast = fast.next
	res = 1
	while slow != fast:
		fast = fast.next
		res += 1
	return res


def countNodesinLoop(head):
	slow = head.next
	fast = head.next
	while fast != None and fast.next != None:
		slow = slow.next
		fast = fast.next.next
		if slow == fast:
			len = 1
			slow = slow.next
			while slow != fast:
				len += 1
				slow = slow.next
			return len
	return 0


def countNodesinLoop(head):
	slow = fast = head
	count = 0
	while slow and fast and fast.next:
		slow = slow.next
		fast = fast.next.next
		if fast == slow:
			count = 1
			ptr = slow
			while ptr.next != slow:
				count += 1
				ptr = ptr.next
			return count
	return 0


def calcLength(n):
	temp = n
	res = 1
	while temp.next != n:
		res += 1
		temp = temp.next
	return res

def countNodesinLoop(head):
	(f, s) = (head, head)
	while f and f.next:
		f = f.next.next
		s = s.next
		if f == s:
			return calcLength(s)
	return 0


def countNodesinLoop(head):
	(f, s) = (head, head)
	while f and f.next:
		f = f.next.next
		s = s.next
		if f == s:
			break
	if not f or not f.next:
		return 0
	s2 = head
	while s2 != s:
		s = s.next
		s2 = s2.next
	cycle_node = s
	curr = s
	i = 0
	while curr:
		i += 1
		curr = curr.next
		if cycle_node == curr:
			break
	return i


def countNodesinLoop(head):
	temp = head
	count = 0
	while temp:
		if temp.data == -2:
			break
		if temp.data == -1:
			temp.data = -2
			count += 1
		else:
			temp.data = -1
		temp = temp.next
	return count


def countNodesinLoop(head):
	slow = head
	fast = head
	ans = 0
	while fast and fast.next:
		fast = fast.next.next
		slow = slow.next
		if slow == fast:
			break
	ans += 1
	slow = slow.next
	if not fast or not fast.next:
		return 0
	else:
		while slow and slow != fast:
			slow = slow.next
			ans += 1
		return ans


def countNodesinLoop(head):
	if head is None:
		return 0
	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 0
	temp = head
	while temp != slow:
		temp = temp.next
		slow = slow.next
	start = temp
	count = 0
	while True:
		temp = temp.next
		count += 1
		if temp == start:
			break
	return count


def countNodesinLoop(head):
	slow = fast = head
	while fast != None and fast.next != None:
		slow = slow.next
		fast = fast.next.next
		if slow == fast:
			temp = slow
			break
	if fast == None or fast.next == None:
		return 0
	temp = temp.next
	count = 1
	while temp != slow:
		count += 1
		temp = temp.next
	return count


def countNodesinLoop(head):
	(slow, fast) = (head, head)
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
		if slow == fast:
			intersection = fast
			slow = head
			while slow != intersection:
				slow = slow.next
				intersection = intersection.next
			start = slow
			temp = start
			c = 1
			while temp.next != start:
				temp = temp.next
				c = c + 1
			return c
	return 0


def countNodesinLoop(head):
	c2 = head
	c1 = head
	flag = False
	while c1 and c1.next and c1.next.next:
		c1 = c1.next.next
		c2 = c2.next
		if c1 == c2:
			flag = True
			break
	if flag:
		temp = c2.next
		cnt = 1
		while temp != c2:
			temp = temp.next
			cnt += 1
		return cnt
	return 0


def countNodesinLoop(head):
	(s, f) = (head, head)
	cur = head
	while f != None and f.next != None:
		s = s.next
		f = f.next.next
		fl = 0
		if s == f:
			s = head
			while s != f and f != None:
				s = s.next
				f = f.next
			fl = 1
		if fl == 1:
			break
	if s != f:
		return 0
	cur = s.next
	cnt = 1
	while cur != s:
		cur = cur.next
		cnt += 1
	return cnt


def countNodesinLoop(head):
	visited = set()
	total = 0
	ptr = head
	x = ptr
	flag = False
	while ptr:
		if ptr in visited:
			x = ptr
			flag = True
			break
		total += 1
		visited.add(ptr)
		ptr = ptr.next
	ptr = head
	count = 0
	if flag == True:
		while ptr:
			if ptr == x:
				return total - count
			else:
				count += 1
				ptr = ptr.next
	return 0


def countNodesinLoop(head):
	flag = 0
	record = 0
	if head == None or head.next == None:
		return 0
	hair = head
	tortoise = head.next.next
	while hair and tortoise and tortoise.next:
		if hair == tortoise:
			flag = 1
			data = hair.data
			break
		tortoise = tortoise.next.next
		hair = hair.next
	if flag == 0:
		return 0
	length = 1
	tortoise = tortoise.next
	while hair != tortoise:
		length += 1
		tortoise = tortoise.next
	return length


def countNodesinLoop(head):
	if not head:
		return
	counter = 0
	d = dict()
	temp = head
	while temp:
		if temp in d:
			return counter - d[temp]
		else:
			d[temp] = counter
		counter += 1
		temp = temp.next
	return 0


def countNodesinLoop(head):
	slow = head
	fast = head
	ptr = None
	while slow and fast and fast.next:
		slow = slow.next
		fast = fast.next.next
		if slow == fast:
			ptr = slow
			break
	if ptr == None:
		return 0
	else:
		cnt = 1
		temp = slow.next
		while temp != slow:
			cnt += 1
			temp = temp.next
		return cnt


def countNodesinLoop(head):
	if head == None or head.next == None:
		return 0
	s = head
	f = s
	t = None
	while f != None and f.next != None:
		s = s.next
		f = f.next.next
		if s == f:
			t = f
			break
	if t == None:
		return 0
	t1 = head
	while t1 != t:
		t = t.next
		t1 = t1.next
	temp = t
	c = 1
	while temp.next != t:
		c = c + 1
		temp = temp.next
	return c


def countNodesinLoop(head):
	if head is None or head.next is None:
		return 0
	slow = head
	fast = head
	entry = head
	len = 1
	while fast.next != None and fast.next.next != None:
		slow = slow.next
		fast = fast.next.next
		if slow == fast:
			while slow != entry:
				slow = slow.next
				entry = entry.next
			temp = entry.next
			while temp and temp != entry:
				len += 1
				temp = temp.next
			return len
	return 0


def countNodesinLoop(head):
	prev = None
	nxt = head
	hasht = {}
	count = 0
	while nxt:
		if nxt in hasht:
			return hasht[prev] - hasht[nxt] + 1
		hasht[nxt] = count
		prev = nxt
		nxt = nxt.next
		count += 1
	return 0


def countNodesinLoop(head):
	p = head
	q = head
	count = 1
	while q != None and q.next != None:
		q = q.next.next
		p = p.next
		if p == q:
			p = p.next
			while q != p:
				p = p.next
				count += 1
			return count
	return 0


def countNodesinLoop(head):
	cur = head
	if head.next == None:
		return 0
	if head.next == head:
		return 1
	c = 0
	while cur != None and type(cur.data) == int:
		c += 1
		cur.data = [cur.data, c]
		cur = cur.next
	if cur == None:
		return 0
	return c - cur.data[1] + 1


def countNodesinLoop(head):
	s = head
	f = head
	while f.next != None and f.next.next != None:
		s = s.next
		f = f.next.next
		if s == f:
			break
	if f == None or f.next == None or f.next.next == None:
		return 0
	if s == f:
		s = head
		while s != f:
			s = s.next
			f = f.next
		ans = 1
		f = f.next
		while s != f:
			f = f.next
			ans += 1
		return ans


def countNodesinLoop(head):
	(start, end) = (head, head)
	while end and end.next:
		start = start.next
		end = end.next.next
		if start == end:
			section = end
			start = head
			while start != end:
				start = start.next
				section = section.next
			slow = start
			temp = slow
			a = 1
			while temp.next != slow:
				temp = temp.next
				a += 1
			return a
	return 0


def countNodesinLoop(head):
	slow_ptr = head
	fast_ptr = head.next
	while slow_ptr != fast_ptr:
		if fast_ptr != None and fast_ptr.next != None:
			slow_ptr = slow_ptr.next
			fast_ptr = fast_ptr.next.next
		else:
			return 0
	fast_ptr = fast_ptr.next
	count = 1
	while slow_ptr != fast_ptr:
		count += 1
		fast_ptr = fast_ptr.next
	return count


def countNodesinLoop(head):
	slow = fast = head
	loopExists = False
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
		if slow == fast:
			loopExists = True
			break
	if loopExists:
		count = 1
		temp = slow
		while temp.next != slow:
			count += 1
			temp = temp.next
		return count
	else:
		return 0


def countNodesinLoop(head):
	slow = head
	fast = head
	while slow and fast and fast.next:
		slow = slow.next
		fast = fast.next.next
		if slow == fast:
			break
	if slow != fast:
		return 0
	else:
		slow = head
		while slow != fast:
			slow = slow.next
			fast = fast.next
		length = 1
		temp = slow.next
		while temp != slow:
			length += 1
			temp = temp.next
		return length


def countNodesinLoop(head):
	slow = head
	fast = head
	boo = True
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
		if slow == fast:
			boo = False
			fast = head
			break
	if boo:
		return 0
	cnt = 1
	while fast.next != slow.next:
		fast = fast.next
		slow = slow.next
	fast = fast.next.next
	slow = slow.next
	while fast != slow:
		fast = fast.next
		cnt += 1
	return cnt