Fast and slow

Why it matters

Corrupted references can make a traversal run forever, and simulations can revisit the same state without an obvious endpoint. Remembering every visited object detects the problem but lets memory grow with the path. For 3 → 2 → 0 → -4 ↩ 2, detect the loop in O(n) time with O(1) extra memory.

You are given the list values head and an index pos where the tail connects (-1 means no cycle). Return whether the list has a cycle.

Input

head = [3, 2, 0, -4], pos = 1

Output

True

In 3 → 2 → 0 → -4 ↩ 2, a one-step traveler and a two-step traveler meet at -4. Their meeting proves a revisit without the brute set of all four seen nodes.

Start slow and fast at node 3. After one round, slow is at 2 and fast is at 0. After two, slow is at 0 while fast has followed -4 back to 2. After three, both are at -4, so the list cycles.

slow advances one link and fast advances two. On a list that ends, fast reaches None and cannot meet slow again. Inside this loop, fast gains one node per round, so the gap closes within one lap. This constant-space test is Floyd's cycle detection.