How do you find the node where a linked list cycle begins?

Q: How do you find the node where a linked list cycle begins?

**Target Audience:** Beginners preparing for coding interviews — you should know what a linked list node is; everything else is explained **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 Picture a jogging track shaped like the letter P. You enter at the bottom of the straight stem, run up it, and then you are on a loop that never lets you out. Two friends start at the entrance together: one jogs, the other runs exactly twice as fast. Because the loop has no exit, the fast runner eventually laps the slow one and they bump into each other somewhere on the loop. Now the clever part. The moment they meet, the slow friend walks back to the entrance, an

The problem

Question presented to candidate: "You are given the head of a singly linked list that may contain a cycle. Return the node where the cycle begins, or None if there is no cycle. Can you do it without extra memory? Please write it in Python."

What a strong answer should cover:

A hash-set baseline (first node seen twice is the entry), O(n) time and O(n) space.
Floyd's tortoise and hare: slow moves 1, fast moves 2; when they meet, restart one pointer at the head and move both by 1 until they meet at the entry.
Why phase 2 works: the meeting distance is a multiple of the cycle length, so mu more steps from the meeting point land on the entry. O(n) time, O(1) space.
Edge cases: empty list, single node with and without a self-loop, cycle back to the head, duplicate values.
Python specifics: compare nodes with is, not ==; a plain class hashes by identity so set() works, but a @dataclass node defines __eq__ and becomes unhashable.

Clarifying questions expected:

"Return the node, or an index? What if there is no cycle?"
"Is O(n) extra memory allowed, and may I modify the list?"

Code / implementation expected: Yes — detect_cycle(head) in Python with two pointers and no extra data structures.

linked-list
cycle

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 — you should know what a linked list node is; everything else is explained 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

Picture a jogging track shaped like the letter P. You enter at the bottom of the straight stem, run up it, and then you are on a loop that never lets you out. Two friends start at the entrance together: one jogs, the other runs exactly twice as fast. Because the loop has no exit, the fast runner eventually laps the slow one and they bump into each other somewhere on

The solution is hidden so you can try first

13 min read · 11 sections

Python code

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

PythonFloyd on lists with and without a cycle

Practice

PythonPhase step counts, and Floyd versus a hash set

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.