DSA-052 · FOCUSED PRACTICE

Find Linked List Cycle Entry

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

Return the exact Node object where a reachable cycle begins, or null if following next eventually terminates. The entry is the first repeated object in a traversal from head. Preserve all input links.

head is null or roots a stable next graph with at most 100,000 distinct reachable nodes: a finite acyclic chain, or a tail of μ≥0 nodes followed by a cycle of length L≥1. Node values are arbitrary ints and may all be equal.
Return the original entry reference, not its value, index, a copied node, or merely the slow/fast meeting point. Return null for an empty or acyclic graph. If the head is already on the cycle, return head.
Neither implementation changes any node value or next field. The identity-set baseline stores visited references; the optimized implementation uses a constant number of references. Concurrent structural changes are outside the contract.

Examples

Input: N0→N1→N2→N3→N4→N5→N6, N6.next=N3
Output: N3
μ=3,L=4. Detection meets at N4 after four rounds; recovery takes three one-step rounds to N3. The meeting is not the answer.
Input: N0→N1→N2→N0
Output: N0
μ=0. The positive-time meeting is already head and recovery performs zero moves.
Input: N0(4)→N1(4)→null
Output: null
Repeated values are not a cycle and must not be returned as an entry.

Before you start

Floyd slow/fast detection (DSA-051)
Identity versus value equality
Modular distance on a cycle

Recognize the structure

This asks for a particular identity inside a repeated path, so a boolean detector alone is incomplete. First establish whether a cycle exists, then use the meeting distance to align a pointer from head with a pointer inside the cycle. No link reversal, marking, or cycle breaking is needed.

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 · 115/20,000 characters

Self-review

I can derive t≡0 modulo L from the detection speeds.I can explain both why μ recovery steps succeed and why fewer cannot.I return an original reference and verify every input edge stays unchanged.

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

Try before revealing

Hint 1

First find a cycle meeting safely. It need not be the entry.

Hint 2

If slow took t steps and fast 2t, what must t satisfy modulo cycle length?

Hint 3

Move a fresh head pointer and the meeting pointer one step each; they first coincide at entry after μ steps.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Return the first repeated identity

Traverse with an IdentityHashMap-backed set. Return the current reference when it is already in the set. For N0→N1→N2→N3→N1, the first repeated object is N1, which is exactly the entry; N0 never repeats because no next edge leads back into the tail. If null is reached, return null. This directly solves the identity problem with O(n) storage and O(n) expected time.

Improve the baseline

Detect at positive time

Use the guarded one-step/two-step loop from DSA-051. A meeting after movement proves a cycle. If the loop exhausts, return null; do not start recovery from a null fast pointer.

Translate the meeting into a congruence

Let t>0 be the number of detection rounds at meeting. Slow took t edges, fast 2t, and both are inside the cycle, so 2t−t=t is divisible by L. The meeting offset from entry is (t−μ) mod L.

Align two equal-speed walkers

Place seeker at head and keep slow at the meeting. Advance each one edge until they are identical. After μ moves seeker reaches entry and slow has offset (t−μ+μ) mod L=t mod L=0. Return that shared reference.

Why it is correct

Meeting exists exactly for cyclic inputs

The detection proof is DSA-051: null exhaustion characterizes acyclic input; within the cycle a relative gap changes by one per round, guaranteeing a meeting. Initial equality is ignored and t is positive.

Recovery has the correct target

At meeting, t≡0 mod L. After μ additional moves from the meeting, slow is at the entry. A fresh seeker from head also reaches entry after μ moves. If μ=0, the meeting is head because its offset is t mod L=0, so the recovery loop correctly does nothing.

No earlier false meeting

For every recovery step r<μ, seeker is in the noncyclic tail while slow stays inside the cycle. These sets are disjoint, so equality cannot occur early. Thus their first equality is exactly the entry, in μ rounds, with every field unchanged.

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 Node cycleEntry(Node head) {
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                Node seeker = head;
                while (seeker != slow) {
                    seeker = seeker.next;
                    slow = slow.next;
                }
                return seeker;
            }
        }
        return null;
    }

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

Read the meaningful blocks

Detect with the original speed ratio

The implementation uses speed one and two. Its reset proof depends on that exact ratio; changing fast to three edges invalidates the t≡0 mod L argument.

Reset a new seeker

Keep slow at its meeting object and initialize seeker=head. The recovery loop advances both by one; leaving fast at speed two does not implement the proof.

Return identity or absence

return seeker is an original reference. The null result belongs only to the detection loop exhausting; matching integer values is never used as a condition.

Complexity

For n distinct reachable nodes, detection takes O(n) rounds and recovery at most μ≤n additional rounds. Total O(n) time, O(1) auxiliary space, no input mutation and no Node allocation.

The identity-set baseline uses O(n) auxiliary references and O(n) expected time under standard identity-map assumptions. The optimized proof handles a self-loop and μ=0 without exceptional arithmetic or division in code.

Exact-state walkthroughs

Reveal normal and boundary traces

Meeting differs from entry: tail three, cycle four

Input: {"values":[0,0,0,0,0,0,0],"entry":3} · Entry identity: "N3"

Step 1 of 10: 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 → N1slowfast
N1: 0next → N2
N2: 0next → N3
N3: 0next → N4
N4: 0next → N5
N5: 0next → N6
N6: 0next → N3

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":0,"next":"N1"},{"id":"N1","value":0,"next":"N2"},{"id":"N2","value":0,"next":"N3"},{"id":"N3","value":0,"next":"N4"},{"id":"N4","value":0,"next":"N5"},{"id":"N5","value":0,"next":"N6"},{"id":"N6","value":0,"next":"N3"}]`
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 Node cycleEntry(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) {
19                 Node seeker = head;
20                 while (seeker != slow) {
21                     seeker = seeker.next;
22                     slow = slow.next;
23                 }
24                 return seeker;
25             }
26         }
27         return null;
28     }
29 
30     public static Node baseline(Node head) {
31         Set<Node> seen = Collections.newSetFromMap(new IdentityHashMap<>());
32         for (Node p = head; p != null; p = p.next)
33             if (!seen.add(p)) return p;
34         return null;
35     }
36 }
37

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":"N1"},{"id":"N1","value":0,"next":"N2"},{"id":"N2","value":0,"next":"N3"},{"id":"N3","value":0,"next":"N4"},{"id":"N4","value":0,"next":"N5"},{"id":"N5","value":0,"next":"N6"},{"id":"N6","value":0,"next":"N3"}]
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":"N1"},{"id":"N1","value":0,"next":"N2"},{"id":"N2","value":0,"next":"N3"},{"id":"N3","value":0,"next":"N4"},{"id":"N4","value":0,"next":"N5"},{"id":"N5","value":0,"next":"N6"},{"id":"N6","value":0,"next":"N3"}]
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":0,"next":"N1"},{"id":"N1","value":0,"next":"N2"},{"id":"N2","value":0,"next":"N3"},{"id":"N3","value":0,"next":"N4"},{"id":"N4","value":0,"next":"N5"},{"id":"N5","value":0,"next":"N6"},{"id":"N6","value":0,"next":"N3"}]
head
"N0"
slow
"N2"
fast
"N4"
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":0,"next":"N1"},{"id":"N1","value":0,"next":"N2"},{"id":"N2","value":0,"next":"N3"},{"id":"N3","value":0,"next":"N4"},{"id":"N4","value":0,"next":"N5"},{"id":"N5","value":0,"next":"N6"},{"id":"N6","value":0,"next":"N3"}]
head
"N0"
slow
"N3"
fast
"N6"
rounds
3
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":0,"next":"N1"},{"id":"N1","value":0,"next":"N2"},{"id":"N2","value":0,"next":"N3"},{"id":"N3","value":0,"next":"N4"},{"id":"N4","value":0,"next":"N5"},{"id":"N5","value":0,"next":"N6"},{"id":"N6","value":0,"next":"N3"}]
head
"N0"
slow
"N4"
fast
"N4"
rounds
4
phase
"detect"
met
true
Keep slow at the meeting and reset only seeker to head.
Detection time t is a multiple of cycle length. After μ equal-speed moves, seeker and slow will both reach entry.
nodes
[{"id":"N0","value":0,"next":"N1"},{"id":"N1","value":0,"next":"N2"},{"id":"N2","value":0,"next":"N3"},{"id":"N3","value":0,"next":"N4"},{"id":"N4","value":0,"next":"N5"},{"id":"N5","value":0,"next":"N6"},{"id":"N6","value":0,"next":"N3"}]
head
"N0"
slow
"N4"
fast
"N4"
rounds
4
phase
"reset"
seeker
"N0"
meeting
"N4"
recoverySteps
0
Move seeker and slow one edge each.
Before μ recovery steps seeker is in the tail and slow is in the cycle; their first equality is exactly the entry. fast remains at its meeting and is no longer used.
nodes
[{"id":"N0","value":0,"next":"N1"},{"id":"N1","value":0,"next":"N2"},{"id":"N2","value":0,"next":"N3"},{"id":"N3","value":0,"next":"N4"},{"id":"N4","value":0,"next":"N5"},{"id":"N5","value":0,"next":"N6"},{"id":"N6","value":0,"next":"N3"}]
head
"N0"
slow
"N5"
fast
"N4"
rounds
4
phase
"recover"
seeker
"N1"
meeting
"N4"
recoverySteps
1
Move seeker and slow one edge each.
Before μ recovery steps seeker is in the tail and slow is in the cycle; their first equality is exactly the entry. fast remains at its meeting and is no longer used.
nodes
[{"id":"N0","value":0,"next":"N1"},{"id":"N1","value":0,"next":"N2"},{"id":"N2","value":0,"next":"N3"},{"id":"N3","value":0,"next":"N4"},{"id":"N4","value":0,"next":"N5"},{"id":"N5","value":0,"next":"N6"},{"id":"N6","value":0,"next":"N3"}]
head
"N0"
slow
"N6"
fast
"N4"
rounds
4
phase
"recover"
seeker
"N2"
meeting
"N4"
recoverySteps
2
Move seeker and slow one edge each.
Before μ recovery steps seeker is in the tail and slow is in the cycle; their first equality is exactly the entry. fast remains at its meeting and is no longer used.
nodes
[{"id":"N0","value":0,"next":"N1"},{"id":"N1","value":0,"next":"N2"},{"id":"N2","value":0,"next":"N3"},{"id":"N3","value":0,"next":"N4"},{"id":"N4","value":0,"next":"N5"},{"id":"N5","value":0,"next":"N6"},{"id":"N6","value":0,"next":"N3"}]
head
"N0"
slow
"N3"
fast
"N4"
rounds
4
phase
"recover"
seeker
"N3"
meeting
"N4"
recoverySteps
3
Return the contract result.
Node labels stand for exact original references, never values. All input edges remain unchanged.
result
"N3"

Cycle begins at head

Input: {"values":[8,8,8],"entry":0} · Entry identity: "N0"

Step 1 of 6: 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: 8next → N1slowfast
N1: 8next → N2
N2: 8next → N0

State after this step
Variable	Value
nodes	`[{"id":"N0","value":8,"next":"N1"},{"id":"N1","value":8,"next":"N2"},{"id":"N2","value":8,"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 Node cycleEntry(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) {
19                 Node seeker = head;
20                 while (seeker != slow) {
21                     seeker = seeker.next;
22                     slow = slow.next;
23                 }
24                 return seeker;
25             }
26         }
27         return null;
28     }
29 
30     public static Node baseline(Node head) {
31         Set<Node> seen = Collections.newSetFromMap(new IdentityHashMap<>());
32         for (Node p = head; p != null; p = p.next)
33             if (!seen.add(p)) return p;
34         return null;
35     }
36 }
37

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":8,"next":"N1"},{"id":"N1","value":8,"next":"N2"},{"id":"N2","value":8,"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":8,"next":"N1"},{"id":"N1","value":8,"next":"N2"},{"id":"N2","value":8,"next":"N0"}]
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":8,"next":"N1"},{"id":"N1","value":8,"next":"N2"},{"id":"N2","value":8,"next":"N0"}]
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":8,"next":"N1"},{"id":"N1","value":8,"next":"N2"},{"id":"N2","value":8,"next":"N0"}]
head
"N0"
slow
"N0"
fast
"N0"
rounds
3
phase
"detect"
met
true
Keep slow at the meeting and reset only seeker to head.
Detection time t is a multiple of cycle length. After μ equal-speed moves, seeker and slow will both reach entry.
nodes
[{"id":"N0","value":8,"next":"N1"},{"id":"N1","value":8,"next":"N2"},{"id":"N2","value":8,"next":"N0"}]
head
"N0"
slow
"N0"
fast
"N0"
rounds
3
phase
"reset"
seeker
"N0"
meeting
"N0"
recoverySteps
0
Return the contract result.
Node labels stand for exact original references, never values. All input edges remain unchanged.
result
"N0"

Acyclic chain has no entry

Input: {"values":[1,2,3],"entry":-1} · Entry identity: null

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: 1next → N1slowfast
N1: 2next → N2
N2: 3next → null

State after this step
Variable	Value
nodes	`[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"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 Node cycleEntry(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) {
19                 Node seeker = head;
20                 while (seeker != slow) {
21                     seeker = seeker.next;
22                     slow = slow.next;
23                 }
24                 return seeker;
25             }
26         }
27         return null;
28     }
29 
30     public static Node baseline(Node head) {
31         Set<Node> seen = Collections.newSetFromMap(new IdentityHashMap<>());
32         for (Node p = head; p != null; p = p.next)
33             if (!seen.add(p)) return p;
34         return null;
35     }
36 }
37

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":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"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":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":null}]
head
"N0"
slow
"N1"
fast
"N2"
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
null

Test the contract

Input: null or a finite null-terminated chain
Output: null
Do not attempt reset without meeting.
Input: N0.next=N0
Output: N0
Self-loop and zero-length tail.
Input: N0→N1→N0
Output: N0
Head is entry, recovery zero moves.
Input: Seven nodes, final next=N3
Output: N3
Meeting N4 differs from entry.
Input: 160 all-equal nodes, final next points to every possible index in turn
Output: Exact node at chosen index
Exhaustive identity and graph-preservation check, including long tail/short cycle.

Common mistakes and counterexamples

Return the first meeting object

Counterexample: For μ=3,L=4, detection meets N4 but the entry is N3.

Reset seeker to head and walk seeker and slow one edge together.

Skip the μ=0 argument

Counterexample: A head cycle may seem to require a special-case search or an extra lap.

The positive-time meeting has offset zero when μ=0; while(seeker!=slow) simply performs zero iterations.

Reset both pointers to head

Counterexample: Every nonempty list would then immediately return head, even when entry is deeper.

Reset only seeker; retain slow at the proven meeting.

Keep fast at speed two during recovery

Counterexample: The two walkers are no longer aligned by the t mod L congruence.

Use identical one-edge steps and test all possible cycle entries for each list length.

Follow-ups

Remove the cycle while retaining every node.

Once the entry is known, traverse the cycle to its predecessor and set that predecessor.next=null. This requires mutation permission and a new postcondition; detection and entry recovery currently promise no writes.

Can fast move three steps instead?

At meeting the difference is 2t, so L divides 2t but need not divide t. With a pure two-node cycle, t=1 can be a meeting away from head; resetting and moving equally can keep the pointers apart forever. Keep the ratio required by the reset proof or derive a different recovery method.

Find the intersection of lists that may contain cycles.

Find each entry first. With neither cycle, use acyclic intersection. With exactly one, intersection is impossible in a stable next graph. With two cycles, check whether entries lie on the same cycle; define what answer means if there is no unique first shared entry across the two heads.

Related foundations

Linked lists: identity, reachability, and update order

Keep practicing

Return to the lesson

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.