How do you detect a cycle in a Linked List? (Floyd's Tortoise and Hare)

Difficulty: 3/10

cycle detection, two-pointer technique, linked list

Floyd's Cycle Detection

Floyd's Tortoise and Hare algorithm detects a cycle using two pointers moving at different speeds. The slow pointer moves one node at a time, while the fast pointer moves two. If a cycle exists, the two pointers will eventually meet inside the cycle.

javascript

1
Time complexity: O(n).
2
Auxiliary space: O(1).
3
The algorithm does not require a HashSet of visited nodes.
4
The meeting point confirms a cycle but is not necessarily the cycle's entry point.
5
The same technique can be extended to locate the cycle entry.

Scenario Questions

0-2 years experience

Follow-up Questions