DSA-051 · Floyd slow/fast cycle detection

Linked List Cycle Detection

Core · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 30093 deterministic checks. Learner drafts are not executed.

Understand the problem

Determine whether following next references from a singly linked list head ever revisits a node. Return a boolean without changing any node or next link.

head may be null. At most 100,000 distinct reachable nodes form an acyclic chain or a tail followed by one cycle. Node.value is any int; values may repeat. The graph is stable for the duration of the call.
A cycle means revisiting the exact same Node object, not seeing the same value. Empty and any finite null-terminated list return false; a self-loop returns true.
The optimized and baseline methods do not write any input fields. They neither mark nodes nor break cycles. The baseline retains identities in an IdentityHashMap-backed set; the optimized method uses O(1) extra references.

Examples

Input: N0(5) → N1(5) → null
Output: false
Equal values at distinct identities do not form a cycle.
Input: N0 → N1 → N2 → N3, with N3.next=N1
Output: true
After three rounds slow and fast meet at N3. The meeting object need not be the cycle entry N1.
Input: N0.next=N0
Output: true
Both pointers move and meet after one round. Initial equality alone is not a test.

Before you start

Node identity, null guards, and singly linked traversal
A finite functional next graph has a tail followed by a cycle or null

Recognize the structure

A next field defines exactly one successor per node, so repeated traversal must either reach null or enter a cycle. A visited identity set is the direct solution. Two speeds replace the retained history because relative position advances by one inside a fixed cycle; this is not about duplicate values or intersecting two separate lists.

Try before revealing

Hint 1

A set of previously visited objects solves the task directly. What does a repeated identity prove?

Hint 2

Inside a cycle, what happens to the relative gap when one pointer moves twice as fast?

Hint 3

Move one and two edges under a null-safe guard, then compare references; null exhaustion means no cycle.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Remember every visited identity

Use a Set<Node> backed by IdentityHashMap. Traverse from head; if adding the current object fails, return true; reaching null returns false. On N0→N1→N2→N1, additions succeed for N0,N1,N2, then the second N1 is already present. On two separate nodes both valued 5, both additions succeed. Time is O(n) under the usual expected constant-time identity-map operations and storage O(n).

Improve the baseline

Choose two traversal speeds

Start slow and fast at head. Within each guarded iteration move slow one edge and fast two. Compare after moving: otherwise their initial equality would incorrectly declare every nonempty chain cyclic.

Guard the two-edge move

fast!=null must be checked before fast.next!=null by Java short-circuit &&. Then fast.next.next is safe to read, even if its value is null. slow is safe whenever the guarded fast move is possible because slow has taken fewer edges on the same path.

Use relative motion after the tail

After slow has entered a cycle of length L, fast is also inside it. On every subsequent round fast gains one cycle position relative to slow. Among at most L rounds the relative distance becomes zero. Return true there; if the guard fails instead, return false.

Why it is correct

Acyclic case

After t completed rounds, slow has followed t edges and fast 2t edges from head. In a null-terminated chain, no two distinct positions name the same node. For t>0 they cannot meet; fast eventually reaches null or a node whose next is null.

Cyclic case

Let μ be the number of edges before the cycle entry and L its positive length. Once t≥μ, both pointers are in the cycle. Their positions relative to the entry differ by t modulo L. A positive multiple of L occurs no later than μ+L rounds (and for μ=0 no later than L), so equality must occur.

Termination and frame preservation

Each iteration either returns or advances fast two edges. Acyclic input exhausts; cyclic input meets by the bound above. No assignment targets a Node field, so every original value and edge, including the back edge of a cycle, is preserved.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.Collections;
import java.util.IdentityHashMap;
import java.util.Set;

public final class Solution {
    public static final class Node {
        public final int value;
        public Node next;
        public Node(int value) { this.value = value; }
    }

    public static boolean hasCycle(Node head) {
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }

    public static boolean baseline(Node head) {
        Set<Node> seen = Collections.newSetFromMap(new IdentityHashMap<>());
        for (Node p = head; p != null; p = p.next)
            if (!seen.add(p)) return true;
        return false;
    }
}

Read the meaningful blocks

Same initial head

The two references initially coincide for empty and nonempty inputs. That coincidence is not evidence of having revisited an object.

Short-circuit guard and advance

Move only inside while(fast!=null && fast.next!=null). Never reverse the guard terms or use ||. The two-step fast reference may become null; comparison to slow is still safe.

Reference equality

slow==fast compares objects. slow.value==fast.value is unrelated to graph repetition. Return false only after the guard can no longer permit another round.

Complexity

Let n be the number of distinct reachable nodes. The optimized method takes O(n) time: O(n) rounds on an acyclic chain or O(μ+L) rounds for a cyclic chain. It uses O(1) auxiliary space and performs no input mutation.

The identity-set baseline visits at most n+1 occurrences and uses O(n) reference storage, with O(n) expected time under standard hash-map assumptions. Neither algorithm needs numeric arithmetic on node values.

Exact-state walkthroughs

Reveal normal and boundary traces

Tail into a three-node cycle

Input: {"values":[5,5,5,5],"entry":1} · Result: true

Step 1 of 5: Start both references at head; initial equality is not a detected cycle.

Pointers have each taken zero edges. No input field will change.

Floyd traversal — original identities and unchanged links

Detection rounds: 0. slow: N0 · fast: N0.

N0: 5next → N1slowfast
N1: 5next → N2
N2: 5next → N3
N3: 5next → N1

Cards stay in original identity order. A next reference to an earlier card is a back edge; equal displayed values do not imply equal nodes. Initial pointer equality is ignored; equality after a movement proves a cycle.

State after this step
Variable	Value
nodes	`[{"id":"N0","value":5,"next":"N1"},{"id":"N1","value":5,"next":"N2"},{"id":"N2","value":5,"next":"N3"},{"id":"N3","value":5,"next":"N1"}]`
head	`"N0"`
slow	`"N0"`
fast	`"N0"`
rounds	`0`
phase	`"initial"`

See the affected Java block

 1 import java.util.Collections;
 2 import java.util.IdentityHashMap;
 3 import java.util.Set;
 4 
 5 public final class Solution {
 6     public static final class Node {
 7         public final int value;
 8         public Node next;
 9         public Node(int value) { this.value = value; }
10     }
11 
12     public static boolean hasCycle(Node head) {
13         Node slow = head;
14         Node fast = head;
15         while (fast != null && fast.next != null) {
16             slow = slow.next;
17             fast = fast.next.next;
18             if (slow == fast) return true;
19         }
20         return false;
21     }
22 
23     public static boolean baseline(Node head) {
24         Set<Node> seen = Collections.newSetFromMap(new IdentityHashMap<>());
25         for (Node p = head; p != null; p = p.next)
26             if (!seen.add(p)) return true;
27         return false;
28     }
29 }
30

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Start both references at head; initial equality is not a detected cycle.
Pointers have each taken zero edges. No input field will change.
nodes
[{"id":"N0","value":5,"next":"N1"},{"id":"N1","value":5,"next":"N2"},{"id":"N2","value":5,"next":"N3"},{"id":"N3","value":5,"next":"N1"}]
head
"N0"
slow
"N0"
fast
"N0"
rounds
0
phase
"initial"
Move slow one edge and fast two under the null guard.
After t rounds slow has taken t edges and fast 2t edges. Equality is tested only after movement and compares identities.
nodes
[{"id":"N0","value":5,"next":"N1"},{"id":"N1","value":5,"next":"N2"},{"id":"N2","value":5,"next":"N3"},{"id":"N3","value":5,"next":"N1"}]
head
"N0"
slow
"N1"
fast
"N2"
rounds
1
phase
"detect"
met
false
Move slow one edge and fast two under the null guard.
After t rounds slow has taken t edges and fast 2t edges. Equality is tested only after movement and compares identities.
nodes
[{"id":"N0","value":5,"next":"N1"},{"id":"N1","value":5,"next":"N2"},{"id":"N2","value":5,"next":"N3"},{"id":"N3","value":5,"next":"N1"}]
head
"N0"
slow
"N2"
fast
"N1"
rounds
2
phase
"detect"
met
false
Move slow one edge and fast two under the null guard.
After t rounds slow has taken t edges and fast 2t edges. Equality is tested only after movement and compares identities.
nodes
[{"id":"N0","value":5,"next":"N1"},{"id":"N1","value":5,"next":"N2"},{"id":"N2","value":5,"next":"N3"},{"id":"N3","value":5,"next":"N1"}]
head
"N0"
slow
"N3"
fast
"N3"
rounds
3
phase
"detect"
met
true
Return the contract result.
Node labels stand for exact original references, never values. All input edges remain unchanged.
result
true

Equal values without a cycle

Input: {"values":[7,7],"entry":-1} · Result: false

Step 1 of 3: Start both references at head; initial equality is not a detected cycle.

Pointers have each taken zero edges. No input field will change.

Floyd traversal — original identities and unchanged links

Detection rounds: 0. slow: N0 · fast: N0.

N0: 7next → N1slowfast
N1: 7next → null

State after this step
Variable	Value
nodes	`[{"id":"N0","value":7,"next":"N1"},{"id":"N1","value":7,"next":null}]`
head	`"N0"`
slow	`"N0"`
fast	`"N0"`
rounds	`0`
phase	`"initial"`

See the affected Java block

 1 import java.util.Collections;
 2 import java.util.IdentityHashMap;
 3 import java.util.Set;
 4 
 5 public final class Solution {
 6     public static final class Node {
 7         public final int value;
 8         public Node next;
 9         public Node(int value) { this.value = value; }
10     }
11 
12     public static boolean hasCycle(Node head) {
13         Node slow = head;
14         Node fast = head;
15         while (fast != null && fast.next != null) {
16             slow = slow.next;
17             fast = fast.next.next;
18             if (slow == fast) return true;
19         }
20         return false;
21     }
22 
23     public static boolean baseline(Node head) {
24         Set<Node> seen = Collections.newSetFromMap(new IdentityHashMap<>());
25         for (Node p = head; p != null; p = p.next)
26             if (!seen.add(p)) return true;
27         return false;
28     }
29 }
30

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Start both references at head; initial equality is not a detected cycle.
Pointers have each taken zero edges. No input field will change.
nodes
[{"id":"N0","value":7,"next":"N1"},{"id":"N1","value":7,"next":null}]
head
"N0"
slow
"N0"
fast
"N0"
rounds
0
phase
"initial"
Move slow one edge and fast two under the null guard.
After t rounds slow has taken t edges and fast 2t edges. Equality is tested only after movement and compares identities.
nodes
[{"id":"N0","value":7,"next":"N1"},{"id":"N1","value":7,"next":null}]
head
"N0"
slow
"N1"
fast
null
rounds
1
phase
"detect"
met
false
Return the contract result.
Node labels stand for exact original references, never values. All input edges remain unchanged.
result
false

One-node self-loop

Input: {"values":[0],"entry":0} · Result: true

Step 1 of 3: Start both references at head; initial equality is not a detected cycle.

Pointers have each taken zero edges. No input field will change.

Floyd traversal — original identities and unchanged links

Detection rounds: 0. slow: N0 · fast: N0.

N0: 0next → N0slowfast

State after this step
Variable	Value
nodes	`[{"id":"N0","value":0,"next":"N0"}]`
head	`"N0"`
slow	`"N0"`
fast	`"N0"`
rounds	`0`
phase	`"initial"`

See the affected Java block

 1 import java.util.Collections;
 2 import java.util.IdentityHashMap;
 3 import java.util.Set;
 4 
 5 public final class Solution {
 6     public static final class Node {
 7         public final int value;
 8         public Node next;
 9         public Node(int value) { this.value = value; }
10     }
11 
12     public static boolean hasCycle(Node head) {
13         Node slow = head;
14         Node fast = head;
15         while (fast != null && fast.next != null) {
16             slow = slow.next;
17             fast = fast.next.next;
18             if (slow == fast) return true;
19         }
20         return false;
21     }
22 
23     public static boolean baseline(Node head) {
24         Set<Node> seen = Collections.newSetFromMap(new IdentityHashMap<>());
25         for (Node p = head; p != null; p = p.next)
26             if (!seen.add(p)) return true;
27         return false;
28     }
29 }
30

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Start both references at head; initial equality is not a detected cycle.
Pointers have each taken zero edges. No input field will change.
nodes
[{"id":"N0","value":0,"next":"N0"}]
head
"N0"
slow
"N0"
fast
"N0"
rounds
0
phase
"initial"
Move slow one edge and fast two under the null guard.
After t rounds slow has taken t edges and fast 2t edges. Equality is tested only after movement and compares identities.
nodes
[{"id":"N0","value":0,"next":"N0"}]
head
"N0"
slow
"N0"
fast
"N0"
rounds
1
phase
"detect"
met
true
Return the contract result.
Node labels stand for exact original references, never values. All input edges remain unchanged.
result
true

Test the contract

Input: null
Output: false
Guard handles empty.
Input: N0→null
Output: false
Initial equality is ignored.
Input: N0.next=N0
Output: true
Smallest cycle.
Input: N0(0)→N1(0)→null
Output: false
Identity matters and fast reaches null.
Input: 160 nodes, tail linked to each possible entry in turn
Output: true for every entry
Exhaust all tail/cycle splits and verify every original edge.

Common mistakes and counterexamples

Compare values instead of references

Counterexample: N0(7)→N1(7)→N2(7)→null has many equal values but no repeated identity.

Use slow==fast and test all-equal acyclic chains.

Compare at initialization

Counterexample: A single node with next=null starts slow==fast and would be falsely rejected.

Check equality only after the guarded movement.

Dereference fast.next before fast

Counterexample: On an even-length acyclic chain, fast can become null.

Use fast!=null && fast.next!=null in that order.

Mark nodes or cut the back edge

Counterexample: Changing a cyclic input to terminate may produce the right boolean while destroying the graph.

Snapshot every next reference before calling both methods and check it remains identical afterward.

Follow-ups

Return the cycle entry instead of a boolean.

A meeting point is generally not the entry. Reset a new pointer to head, move it and the meeting pointer one edge per round, and use the distance congruence proved in DSA-052.

Find the cycle length and tail length.

After detecting a meeting, hold one reference fixed and count a full lap with another. Find the entry, then count edges from head to it for μ. Do not count repeated values.

Detect a cycle in a general directed graph.

Floyd relies on exactly one successor. Multiple outgoing edges require DFS with active-path coloring or another graph algorithm; a globally visited node can represent a shared subgraph rather than a cycle.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 101/20,000 characters

Self-review

I can state slow and fast edge counts after t rounds.I can prove a meeting occurs without assuming it happens at the entry.I use object equality and preserve every next link.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Linked lists: identity, reachability, and update order

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-16 · Original teaching content and implementations authored for AceYourInterviews. Familiar problem names describe standard algorithmic tasks; no company-frequency or platform-difficulty claims are made.