Given a linked list of N nodes. The task is to check if the linked list has a loop. Linked list can contain self loop.
Example 1:
Input:
N = 3
value[] = {1,3,4}
x(position at which tail is connected) = 2
Output: True
Explanation: In above test case N = 3.
The linked list with nodes N = 3 is
given. Then value of x=2 is given which
means last node is connected with xth
node of linked list. Therefore, there
exists a loop.
Example 2:
Input:
N = 4
value[] = {1,8,3,4}
x = 0
Output: False
Explanation: For N = 4 ,x = 0 means
then lastNode->next = NULL, then
the Linked list does not contains
any loop.
Your Task:
The task is to complete the function detectloop() which contains reference to the head as only argument.  This function should return true if linked list contains loop, else return false.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{4}
1 ≤ Data on Node ≤ 10^{3}

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 check if the linked list has a loop.

    def detectLoop(self, head):

        #code here

Solutions:
class Solution:

	def detectLoop(self, head):
		s = set()
		if not head:
			return False
		curr = head
		while curr:
			if curr in s:
				return True
			s.add(curr)
			curr = curr.next
		return False


class Solution:

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


class Solution:

	def detectLoop(self, head):
		(s, f) = (head, head)
		while f and f.next:
			s = s.next
			f = f.next.next
			if s == f:
				return True
		return False


class Solution:

	def detectLoop(self, head):
		x = head
		y = head
		while x and x.next is not None:
			x = x.next.next
			y = y.next
			if x == y:
				return True
		return False


class Solution:

	def detectLoop(self, head):
		Freq = {}
		temp = head
		while temp != None:
			if temp not in Freq:
				Freq[temp] = True
			else:
				return True
			temp = temp.next
		return False


class Solution:

	def detectLoop(self, head):
		if head is None:
			return False
		slow = head
		fast = head.next
		while slow != fast:
			if fast is None or fast.next is None:
				return False
			fast = fast.next.next
			slow = slow.next
		return True


class Solution:

	def detectLoop(self, head):
		if head is None:
			return False
		slow = head
		fast = head.next
		while fast is not None and fast.next is not None and (slow is not None):
			if fast.next == slow:
				return True
			else:
				fast = fast.next.next
				slow = slow.next
		try:
			if fast.next == slow:
				return True
		except:
			a = 1
		return False


class Solution:

	def detectLoop(self, head):
		if not head or not head.next:
			return False
		hashMap = {}
		prev = None
		curr = head
		while curr:
			if hashMap.get(curr, None):
				return True
			hashMap[curr] = 1
			curr = curr.next
		return False


class Solution:

	def detectLoop(self, head):
		s = set()
		temp = head
		while temp:
			if temp in s:
				return True
			s.add(temp)
			temp = temp.next
		return False


class Solution:

	def detectLoop(self, head):
		FastPointer = head
		SlowPointer = head
		while SlowPointer != None and FastPointer != None and (FastPointer.next != None):
			SlowPointer = SlowPointer.next
			FastPointer = FastPointer.next.next
			if SlowPointer == FastPointer:
				return True
		return False


class Solution:

	def detectLoop(self, head):
		fst = slow = head
		while fst and fst.next:
			fst = fst.next.next
			slow = slow.next
			if fst == slow:
				return True
		return False


class Solution:

	def detectLoop(self, head):
		temp = head
		lamp = head
		while lamp and lamp.next:
			temp = temp.next
			lamp = lamp.next.next
			if temp == lamp:
				return True
		return False


class Solution:

	def detectLoop(self, head):
		if head is None:
			return False
		slowPtr = head
		fastPtr = head
		while fastPtr is not None and fastPtr.next is not None:
			slowPtr = slowPtr.next
			fastPtr = fastPtr.next.next
			if slowPtr == fastPtr:
				return True
		return False


class Solution:

	def detectLoop(self, head):
		curr = head
		curr_idx = 0
		if curr == None:
			return False
		if curr.next == None:
			return False
		while curr_idx < n - 2:
			curr.data = curr_idx + 1
			curr = curr.next
			curr_idx += 1
		curr.data = curr_idx + 1
		if curr.next.next == None:
			return False
		if curr.next.next.data <= curr.data:
			return True


class Solution:

	def detectLoop(self, head):
		current = head
		while current:
			if not current.data:
				return True
			else:
				current.data = 0
			current = current.next
		return False


class Solution:

	def detectLoop(self, head):
		if not head or not head.next:
			return False
		slow_step = head
		fast_step = head
		while slow_step and fast_step and fast_step.next:
			slow_step = slow_step.next
			fast_step = fast_step.next.next
			if slow_step == fast_step:
				return True
		return False


class Solution:

	def detectLoop(self, head):
		hashMap = {}
		current = head.next
		while current:
			isExist = hashMap.get(current.next, 0)
			if isExist:
				return True
			hashMap[current.next] = 1
			current = current.next
		return False


class Solution:

	def detectLoop(self, head):
		if head is None or head.next is None:
			return False
		slow_pointer = head
		fast_pointer = head.next
		while fast_pointer.next and fast_pointer.next.next:
			if slow_pointer == fast_pointer:
				return True
			fast_pointer = fast_pointer.next.next
			slow_pointer = slow_pointer.next
		return False


class Solution:

	def detectLoop(self, head):
		(p, q) = (head, head)
		while q != None and q.next != None:
			p = p.next
			q = q.next.next
			if p == q:
				return True
		return False


class Solution:

	def detectLoop(self, head):
		seen = set()
		while head is not None:
			if head in seen:
				return True
			else:
				seen.add(head)
			head = head.next
		return False


class Solution:

	def detectLoop(self, head):
		if not head:
			return
		(turtle, hare) = (head, head)
		while hare.next and hare.next.next:
			turtle = turtle.next
			hare = hare.next.next
			if turtle == hare:
				return True
		return False


class Solution:

	def detectLoop(self, head):
		(n, m) = (head, head)
		while m and m.next:
			n = n.next
			m = m.next.next
			if n == m:
				return True
		return False


class Solution:

	def detectLoop(self, head):
		slow_p = head
		fast_p = head
		while True:
			if slow_p is None or fast_p is None:
				return False
			slow_p = slow_p.next
			if fast_p.next is None:
				return False
			fast_p = fast_p.next.next
			if fast_p == slow_p:
				return True
		return False


class Solution:

	def detectLoop(self, head):
		if head is None or head.next is None:
			return False
		slow = head
		fast = head.next
		while id(slow) != id(fast):
			slow = slow.next
			if fast is None:
				break
			fast = fast.next
			if fast is None:
				break
			fast = fast.next
		return id(slow) == id(fast)


class Node:

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

class Solution:

	def detectLoop(self, head):
		slow = head
		fast = head
		while slow and fast and fast.next:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				return True
		return False


class Solution:

	def detectLoop(self, head):
		front = head
		second = head.next
		while second != None:
			if front == second:
				return True
			front = front.next
			if second.next is not None:
				second = second.next.next
			else:
				second = second.next
		return False


class Solution:

	def detectLoop(self, head):
		tortoise = head
		hare = head
		while hare is not None and hare.next is not None:
			tortoise = tortoise.next
			hare = hare.next.next
			if tortoise == hare:
				return True
		return False


class Solution:

	def detectLoop(self, head):
		(tortoise, rabbit) = (head, head)
		while rabbit and rabbit.next:
			tortoise = tortoise.next
			rabbit = rabbit.next.next
			if tortoise == rabbit:
				return True
		return False


class Solution:

	def detectLoop(self, head):
		st = set()
		cur = head
		while cur and (not cur in st):
			st.add(cur)
			cur = cur.next
		return True if cur else False


class Solution:

	def detectLoop(self, head):
		if head.next != None:
			tail = head
			head1 = head.next
			while head1 != None and head1.next != None and (head1 != tail):
				tail = tail.next
				head1 = head1.next.next
			return head1 == tail
		else:
			return False


import collections

class Solution:

	def detectLoop(self, head):
		slow = head
		fast = head
		while fast.next and fast.next.next:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				return True
		return False


class Solution:

	def detectLoop(self, head):
		t = head
		h = head
		while h != None and h.next != None:
			t = t.next
			h = h.next.next
			if t == h:
				return True
		return False


class Solution:

	def detectLoop(self, head):
		if not head or not head.next:
			return False
		slow = head
		fast = head.next
		while slow != fast:
			if not fast or not fast.next:
				return False
			slow = slow.next
			fast = fast.next.next
		return True


class Solution:

	def detectLoop(self, head):
		mp = {}
		temp = head
		while temp:
			if mp.get(temp):
				return True
			mp[temp] = temp
			temp = temp.next
		return False


class Solution:

	def detectLoop(self, head):
		a = head
		b = head
		while b and b.next:
			a = a.next
			b = b.next.next
			if a == b:
				return True
		return False


class Solution:

	def detectLoop(self, head):
		next_node = head
		counter = 0
		while next_node and counter <= 10000:
			next_node = next_node.next
			counter += 1
		if next_node is None:
			return False
		elif counter == 1000:
			return True
		else:
			return True


class Solution:

	def detectLoop(self, head):
		my_dict = {}
		temp = head
		while temp:
			if my_dict.get(temp):
				return True
			else:
				my_dict[temp] = True
				temp = temp.next
		return False


class Solution:

	def detectLoop(self, head):
		if head == None:
			return False
		single = head
		double = head.next
		while single != None and double != None and (double.next != None):
			if single == double or single == double.next:
				return True
			single = single.next
			double = double.next.next
		return False


class Solution:

	def detectLoop(self, head):
		ptr1 = head
		ptr2 = head
		while ptr2 is not None and ptr2.next is not None:
			ptr1 = ptr1.next
			ptr2 = ptr2.next.next
			if ptr1 == ptr2:
				return True
		return False


class Solution:

	def detectLoop(self, head):
		(slow, fast) = (head, head)
		while fast is not None and fast.next is not None:
			slow = slow.next
			fast = fast.next.next
			if id(slow) == id(fast):
				return True
		return False