Neural Mastery
← Practice
Linked List Cycle Detectioneasy

Linked List Cycle Detection

easy Coding Interview Patterns 10–15 min

NumPy allowed · plain Python earns 10 bonus points

Implement Floyd's Tortoise and Hare cycle detection -- two pointers moving at different speeds are GUARANTEED to meet inside any cycle, using O(1) extra space instead of an O(n)-space visited-set.

Related Skills

Task

Implement has_cycle(values, pos): build the linked list from values, wiring the last node's next to index pos if pos != -1. Then walk a slow pointer one step at a time and a fast pointer two steps at a time; if they ever point to the exact same node, a cycle exists.

Function Signature

has_cycle(values: list[int], pos: int) -> bool

Examples

Example 1: Cycle Back to Index 1
Input: values = [3, 2, 0, -4] pos = 1
Output: True
Example 2: Two-Node Cycle to Head
Input: values = [1, 2] pos = 0
Output: True

Constraints

  • Libraries are allowed; a plain-Python solution earns 10 bonus points.
  • Must run in O(1) extra space -- a set of visited node ids works but does not satisfy the intended solution.
  • pos = -1 means no cycle; otherwise pos is a valid 0-indexed position in `values`.
Python3Saved ✓
def has_cycle(values: list[int], pos: int) -> bool:
"""values: the node values, in list order. pos: the 0-indexed
position the LAST node's next pointer connects back to (creating a
cycle), or -1 for no cycle. First build the described linked list
(wiring the cycle if pos != -1), then use Floyd's slow/fast pointer
technique to detect whether it contains a cycle. Must run in O(1)
extra space (not a set of visited node ids)."""
# Your implementation here
pass

Case 1: Cycle Back to Index 1
Input: values = [3, 2, 0, -4] pos = 1
Expected: True
Case 2: Two-Node Cycle to Head
Input: values = [1, 2] pos = 0
Expected: True