Which algorithm is used to detect a cycle in a singly linked list and to report the cycle length once detected?

• A. Floyd’s Tortoise and Hare algorithm
• B. Brent's cycle detection algorithm
• C. Karp's algorithm
• D. Hash-based visited set

Answer: (A)

Floyd’s Tortoise and Hare algorithm is the classic way to detect a cycle in a singly linked list and to find its length. The idea is simple but powerful: run two pointers through the list at different speeds—the slow pointer moves one node at a time, the fast pointer moves two nodes at a time. If there’s no cycle, the fast pointer will eventually reach the end of the list (null) and you know there’s no cycle. If a cycle exists, the fast pointer will eventually lap the slow pointer, and they will meet inside the cycle. This meeting confirms a cycle without needing extra storage.

Once they meet, you can determine the cycle’s length by keeping one pointer fixed at the meeting point and moving the other pointer around the cycle until it returns to that same node, counting the steps along the way. Because every full traversal of the cycle comes back to the starting meeting point, the counted steps equal the number of nodes in the cycle.

This method uses only constant extra space and runs in linear time, making it a preferred approach for both detecting a cycle and reporting its length. Other approaches like hashing visited nodes can detect a cycle but require additional memory, and while other cycle-detection methods exist, Floyd’s routine is the standard way to obtain the cycle length directly after detection.