HardLow-Level DesignAsked in 20246 min read

Detect a Cycle in a Linked List (Floyd's Tortoise and Hare)

Q: Detect a Cycle in a Linked List (Floyd's Tortoise and Hare)

**Target Audience:** Engineers preparing for practical JavaScript coding interviews. **Difficulty:** Hard > **How to read this doc:** all 5 real linked-list shapes below — a genuinely acyclic list, a list with a real cycle, a single node, a single self-referencing node, and an empty list — were verified directly, each producing the exact correct boolean result. ## 1. The problem, restated Detect whether a linked list, followed via its own `next` pointers, ever loops back on itself — using genuinely CONSTANT extra space, not a real `Set` tracking every node visited so far (which would work correctly but cost O(n) space). ## 2. Clarifying questions a strong candidate asks | Question | Why it matters | | :--- | :--- | | O(1) space genuinely required? | Yes, the real, defining constraint of this specific question — a Set-based O(n) approach is a real, valid, SIMPLER alternative worth naming, but this question specifically tests the more elegant, constant-space technique. | | Single-no

1.6k views

140 of 154

The problem

Problem, as an interviewer would state it: "Given the head of a linked list, determine whether it contains a cycle — using O(1) extra space, not a real Set tracking every visited node."

Examples:

Code

hasCycle(acyclicListHead); // false
hasCycle(cyclicListHead);  // true

Clarifying questions expected:

Is O(1) extra space genuinely required, or would an O(n)-space visited-set approach be acceptable?
Should this also work correctly for a single-node list, including one that points to itself?
Does the function need to return WHERE the cycle begins, or just whether one exists at all?

Code / implementation expected: Yes — real, direct proof across 5 real linked-list shapes: acyclic, genuinely cyclic, a single node, a self-referencing single node, and an empty list.

js-coding
utility
algorithm

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: Engineers preparing for practical JavaScript coding interviews. Difficulty: Hard

How to read this doc: all 5 real linked-list shapes below — a genuinely acyclic list, a list with a real cycle, a single node, a single self-referencing node, and an empty list — were verified directly, each producing the exact correct boolean result.

1. The problem, restated

Detect whether a linked list, followed via its own next pointers, ever loops back on itself — using genuinely CONSTANT extra space, not a real Set tracking every node visited so far (which would work correctly but cost O(n) space).

2. Clarifying questions a strong candidate asks

Question	Why it matters
O(1) space genuinely required?	Yes, the real, defining constraint of this specific question — a Set-based O(n) approach is a real, valid, SIMPLER alternative worth na

The solution is hidden so you can try first

6 min read · 9 sections

Run the code

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

JavaScriptReal, direct proof: hasCycle() produces the correct result across 5 real linked-list shapes, including a self-referencing single node and an empty list

Practice

Discussion

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

No comments yet. Share how you would answer it.

Question 140 of 154 in JavaScript coding

Keep your momentum going.

Mark this question solved to track your progress, then take the next one while it is fresh.

All JavaScript coding questions

Up nextHard→

Build a Minimal jest.fn()-Style Spy/Mock Utility

Continue