Explanation
- Floyd’s Cycle Detection Algorithm, also known as Tortoise and Hare, is used to detect if there is a cycle in a linked list. It uses two pointers moving at different speeds.
- Steps:
- Initialize two pointers,
slowandfast, both starting at the head of the list. - Move
slowone step andfasttwo steps in each iteration. - If there is a cycle,
slowandfastwill eventually meet. - If
fastorfast.nextbecomesNone, there is no cycle.
- Initialize two pointers,
Time Complexity
- O(n), where
nis the number of nodes in the linked list.
class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
# Example usage
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
print("Has Cycle:", has_cycle(head))