Google Interview Question

Question 2: Explain how you would detect a cycle in a linked list.

Interview Answer

Anonymous

Aug 18, 2024

Approach: Use the Floyd's Tortoise and Hare algorithm. Have two pointers: a slow pointer that moves one step at a time and a fast pointer that moves two steps at a time. If the linked list has a cycle, the fast pointer will eventually meet the slow pointer inside the cycle. If the fast pointer reaches the end (i.e., null), there is no cycle.