How do you detect a cycle in a linked list? | Interview Question

Q: How do you detect a cycle in a linked list?

**Target Audience:** Beginners preparing for coding interviews — no prior algorithms knowledge assumed **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact word an interviewer expects. All code is Python, and every output block in the **Verified** section was copied from a real run of the examples on this page. ## 1. Why This Even Matters — A Story First You are following signposts through a huge forest park: each post points to the next one, and the last post should point to the exit. But someone has knocked a post round, and now it points back to a post you passed earlier. If that happened, you will walk in circles for ever, and since every post looks the same, you cannot tell just by looking. Option one: tie a ribbon on every post you pass. If you ever reach a post that already has your ribbon, you are going in circles. That works, but you need

The problem

Question presented to candidate: "Given the head of a linked list, tell me whether it contains a cycle, meaning some node's next pointer leads back to an earlier node. Write it in Python. Can you do it with constant extra memory?"

What a strong answer should cover:

The simple approach: remember visited nodes in a hash set; O(n) time and O(n) space.
Floyd's tortoise and hare: one pointer moves one step, the other two; they meet if and only if there is a cycle; O(n) time and O(1) space.
Why they must meet: inside the loop the gap shrinks by exactly one node per round, so it cannot be skipped.
Comparing node identity, not values, and handling the empty list, one node, and a node that points to itself.
The follow-ups: cycle length, and where the cycle starts (reset one pointer to the head).
Python specifics: identity with is, why a set of nodes works with the default hash but not with a @dataclass node, and checking fast is not None before fast.next.

Clarifying questions expected:

"Do you only need true or false, or also where the cycle starts?"
"May I modify the list (for example mark visited nodes), or must it stay unchanged?"

Code / implementation expected: Yes — a Python has_cycle(head) using Floyd's algorithm, ideally after describing the hash-set version.

linked-list
pointers

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — no prior algorithms knowledge assumed Difficulty: Medium Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact word an interviewer expects. All code is Python, and every output block in the Verified section was copied from a real run of the examples on this page.

1. Why This Even Matters — A Story First

You are following signposts through a huge forest park: each post points to the next one, and the last post should point to the exit. But someone has knocked a post round, and now it points back to a post you passed earlier. If that happened, you will walk in circles for ever, and since every post looks the same, you cannot tell just by looking.

Option one: tie a ribbon on every post you pass. If you

The solution is hidden so you can try first

13 min read · 12 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonFloyd and a hash set on cyclic and acyclic lists

Practice

PythonMeeting step, cycle length and cycle start on a 10,000-node list

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.