time O(N) space O(1)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if not head:
return False
sl,fa = head,head
# can be also written while fa and fa.next , main idea is to loop turil fast ptr reached to end of linked list
while fa.next and fa.next.next: # loop termination condition is bounded to fast pointer
fa = fa.next.next
sl = sl.next
if fa == sl:
return True
return False
About Floyd’s Tortoise and Hare Algorithm (Floyd’s Cyclec Detection algorithm): main idea if you have two pointers in a Singly Linked list, one moving twice as fast (the hare) than the other (the tortoise), then if they intersect, there is a cycle in the linked list. If they don’t intersect, then there is no cycle.