PPractick

The problem

A bug in a job scheduler occasionally makes the last task in a linked list point back to an earlier task, creating a cycle. Any code that walks the list then spins forever. The monitor needs to detect this. A hash set of visited nodes works but uses O(n) memory. Floyd's cycle detection (tortoise and hare) uses O(1): move a slow pointer one step and a fast pointer two steps. If there's no cycle, fast reaches the end; if there is one, fast eventually laps slow and they meet.

Example: 3 -> 2 -> 0 -> -4, with -4 linking back to 2 → true.

Function signature

bool hasCycle(Node* head);

Test cases

Input (values, tail links to index)	Output	Explanation
[3, 2, 0, -4], pos 1	true	-4 links back to 2
[1, 2], pos 0	true	2 links back to 1
[1], pos 0	true	A self-loop
[1], pos -1	false	No cycle
[1, 2, 3], pos -1	false
[]	false	Empty list

(Confirm: pos is the index the tail links back to, or -1 for no cycle; pos is used only to build the test, the function receives just the head.)

How interviewers phrase it

• "Determine whether a linked list has a cycle" (LeetCode 141).
• "Can you do it in O(1) memory?"
• The first step of "find where the cycle starts" (S.No 162) and "length of the loop" (S.No 163).

Clarifying questions to ask

1. Can I modify the list (for example, mark visited nodes)?
2. Is O(1) extra space required?
3. Return a boolean or the meeting node?

Follow-ups to expect

1. "Why must the pointers meet if there's a cycle?"
2. "Why step 2 and not 3?"
3. "What's the hash-set approach?"
4. "How long does Floyd's take?"
5. "Complexity?"

Related questions

• Find the starting point in LL Medium
• Length of loop in LL Medium
• Check if LL is palindrome or not Medium
• Remove Nth node from the back of the LL Medium
• Delete the middle node in LL Medium
• Find the intersection point of Y LL Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in