Coding Patterns Easy Asked at AmazonAsked at GoogleAsked at Meta

Detect whether a linked list has a cycle using Floyd's fast/slow pointer algorithm.

For Data Scientist ML Engineer Data Engineer AI / LLM Engineer

The short answer

Two pointers start at the head — slow moves one step, fast moves two. If there is a cycle, fast laps slow and they meet inside the cycle. If fast reaches None, there is no cycle. This runs in O(n) time with O(1) space, no hash set needed.

How to think about it

Recognise the pattern

Fast/slow pointers (Floyd’s tortoise and hare) solve any problem about cycles or midpoints in a linked list. The signals:

Detect a cycle with O(1) space.
Find the start of a cycle.
Find the middle of a list (slow pointer ends up there when fast reaches the end).

Whenever you need to reason about relative speeds in a linear structure, think two pointers at different rates.

Build the approach step by step

Hash-set approach: track every visited node address. If you see a node twice, there is a cycle. O(n) time but O(n) space — the interviewer will push you to do better.

Floyd’s algorithm:

Intuition: imagine two runners on a circular track. The faster runner will inevitably lap the slower one and they will meet. If the track is linear (no cycle), the faster runner simply falls off the end.

slow advances 1 node per step.
fast advances 2 nodes per step.
If fast or fast.next is None, the list is acyclic — return False.
If slow == fast, they have met — there is a cycle — return True.

List: 1 -> 2 -> 3 -> 4 -> 2 (cycle back to node 2)

Step 0: slow=1, fast=1
Step 1: slow=2, fast=3
Step 2: slow=3, fast=2   (fast wrapped around the cycle)
Step 3: slow=4, fast=4   -> MEET -> cycle detected

Complexity

	Value	Why
Time	O(n)	Fast pointer enters the cycle, then closes the gap in at most cycle-length steps
Space	O(1)	Only two pointers

Finding the cycle start (LC 142)

Once slow and fast meet inside the cycle, reset one pointer to head. Advance both one step at a time — they will meet again exactly at the cycle’s entry node. This works because of a neat mathematical property of the distances involved.

After meeting: reset a = head, b = meeting_point
while a is not b:
    a = a.next
    b = b.next
return a  # cycle start