# The Cycle Detector

> Follow the chain long enough and you might end up where you started.

Canonical URL: <https://datadriven.io/problems/the_cycle_detector>

Domain: Python · Difficulty: medium · Seniority: L3

## Problem

Given a list where each index i has next_pointers[i] = next index (or -1 for tail), return True if starting from any index leads to a cycle. Actually: follow starting from index 0 and detect whether any index is revisited before hitting -1 or out-of-range.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests the **Floyd's cycle detection (tortoise and hare)** algorithm or set-based visited tracking. It probes whether a candidate can traverse a linked structure and detect revisits efficiently.

> **Trick to Solving**
>
> Use a visited set: as you follow `next` pointers, add each node index to the set. If you visit the same index twice, there is a cycle. Alternatively, use two pointers moving at different speeds.

---

### Break down the requirements

#### Step 1: Start at node 0 and follow next pointers

Each node's value is the index of the next node, or -1 for the tail.

#### Step 2: Track visited nodes

Use a set to record every index you visit. If you see a repeat, return `True`.

#### Step 3: Return False if you reach -1

Reaching -1 means you hit the tail without revisiting any node.

---

### The solution

**Visited set traversal**

```python
def has_cycle(nodes: list) -> bool:
    visited = set()
    current = 0
    while current != -1 and current < len(nodes):
        if current in visited:
            return True
        visited.add(current)
        current = nodes[current]
    return False
```

> **Time and Space Complexity**
>
> **Time:** O(n) where n is the number of nodes. Each node is visited at most once.
> 
> **Space:** O(n) for the visited set. Floyd's algorithm achieves O(1) space.

> **Interviewers Watch For**
>
> Whether you mention Floyd's tortoise-and-hare as an O(1) space alternative. The set approach is correct but not optimal.

> **Common Pitfall**
>
> Not guarding against invalid indices. A node's next pointer could reference an out-of-bounds index; treat that as a termination like -1.

---

## Common follow-up questions

- How would you detect the cycle start node? _(Tests Floyd's phase 2: reset one pointer to head and advance both at speed 1.)_
- What is the O(1) space approach? _(Tests Floyd's algorithm with slow and fast pointers.)_
- What if the list uses actual node objects instead of an array? _(Tests adapting from index-based to pointer-based traversal.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_cycle_detector)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.