Loading…

easyLinked ListsLC #141Frequently asked

Linked List Cycle Detection

Q: How do you solve Linked List Cycle Detection using the Hash Set — Remember Visited Nodes approach?

When to use it: State it first as the intuitive baseline, then offer Floyd's to save the O(n) space. Walk the list one node at a time, recording each node you visit in a hash set of node references. If you ever reach a node that's already in the set, you must have followed `next` back to somewhere you've been — that's a cycle. **Why store node references, not values.** Two different nodes can hold the same `val` (the list `[1, 1]` with no cycle is perfectly legal). Hashing on identity — the object reference in Java, `id()`-style identity via the object itself in Python — guarantees we only flag a true revisit, not a coincidental value match. **Why it terminates.** A finite list with no cycle ends at `null`, so the loop exits and we return `false`. A list with a cycle has no `null`, but it has only finitely many distinct nodes, so within n steps we are forced to land on one we've already stored. **Why we still prefer Floyd's.** This is correct and easy to explain, but it spends O(n) memory to remember every node. The fast/slow pointer method gets the same answer in O(1) space, which is what an interviewer is usually fishing for once you've shown the baseline. Time complexity: O(n). Space complexity: O(n).

Q: How do you solve Linked List Cycle Detection using the Floyd's Tortoise & Hare — Fast/Slow Pointers (Optimal) approach?

When to use it: The answer they want. Phrase it as 'a fast runner laps a slow runner on a circular track'. Two pointers leave the head together; `slow` takes single steps, `fast` takes double steps. On a straight (acyclic) list `fast` simply runs off the end. On a cyclic list `fast` is condemned to loop forever and will inevitably catch up to `slow` from behind. **Why they are guaranteed to meet.** Once both pointers are inside the cycle, consider the distance from `fast` to `slow` measured *forward around the loop*. Every step, `slow` gains 1 and `fast` gains 2, so that gap shrinks by exactly 1 each step. A quantity that decreases by 1 each step (modulo the cycle length) must eventually hit 0 — meaning they land on the same node. Crucially, because the gap changes by 1, fast can never 'leap over' slow without first matching it. **Why the loop guard is `fast != null && fast.next != null`.** `fast` reads `fast.next.next` each iteration. If `fast` is null we'd crash on `fast.next`; if `fast.next` is null we'd crash on the second hop. Both conditions being true is exactly what guarantees the double step is safe — and either being false means we hit the end of an acyclic list, so we return false. **Why identity comparison.** We test `slow == fast` on the node *references*. Comparing `slow.val == fast.val` is a classic bug: distinct nodes routinely share values, which would report phantom cycles. **Memory win.** We replaced the hash set's O(n) bookkeeping with two integer-sized pointers. Same O(n) time, but O(1) space — the upgrade interviewers are listening for. Time complexity: O(n). Space complexity: O(1).

LCPractice

Linked List · 2 of 24 · 8 min

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle if some node can be reached again by continuously following the next pointer. Return true if there is a cycle, otherwise return false. You should not modify the list.

In plain English

We only answer yes/no: does following next forever loop, or does it terminate at null? We don't return the cycle's location here (that's LeetCode 142). A node's next pointing back to any earlier node — including itself — counts as a cycle.

Examples

Example 1

Input: head = [3, 2, 0, -4], pos = 1 (tail connects to index 1)
Output: true
Note: The tail node -4 points back to node 2, forming a cycle 2 → 0 → -4 → 2.

Example 2

Input: head = [1, 2], pos = 0
Output: true
Note: The tail node 2 points back to the head, so the two nodes cycle forever.

Example 3

Input: head = [1], pos = -1
Output: false
Note: A single node whose next is null terminates — no cycle.

Constraints

The number of nodes is in the range [0, 10⁴]
-10⁵ ≤ Node.val ≤ 10⁵
The cycle, if present, is created by the tail's next pointing to an earlier node (or to itself)

Clarifying questions4First question: Can a node's next point to itself?Explore questions

Q1.Can a node's next point to itself?
Yes — a single node whose next is itself is a valid one-node cycle and must return true.
Q2.Am I allowed to modify the list (e.g. mark visited nodes)?
I'll treat the list as read-only. Floyd's needs no mutation; marking nodes would corrupt the input and is fragile.
Q3.Do you also need where the cycle begins?
Not for this problem — just true/false. If you did, I'd add Floyd's phase two: reset one pointer to head and walk both one step at a time.
Q4.What about the empty list or a single node with no cycle?
Empty list and a lone node with next = null both return false; the while-loop guard handles them without special-casing.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Run two pointers from the head: slow moves one node per step, fast moves two. If there's a cycle, fast eventually laps slow and they meet — return true. If fast reaches null, the list ends, so there's no cycle — return false. This is Floyd's Tortoise and Hare: O(n) time, O(1) space. A hash set of visited nodes also works but costs O(n) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know the O(1)-space fast/slow trick instead of defaulting to a hash set, and whether you guard the fast pointer's two-step advance against null.

Where candidates slip

Dereferencing fast.next.next without checking fast and fast.next first, or comparing node values instead of node identity.

How to stand out

State the hash-set baseline, then upgrade to Floyd's for O(1) space. Explain *why* they must meet (the gap shrinks by one each step) and mention the cycle-entry extension.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Hash Set — Remember Visited Nodes	`O(n)`	`O(n)`	State it first as the intuitive baseline, then offer Floyd's to save the O(n) space.	Read
2	Floyd's Tortoise & Hare — Fast/Slow Pointers (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'a fast runner laps a slow runner on a circular track'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewDoes the list contain a cycle?Is O(1) extra space required?YesNo / need visited setExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Hash Set — Remember Visited Nodes

TimeO(n)SpaceO(n)

State it first as the intuitive baseline, then offer Floyd's to save the O(n) space.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you walk the list and keep a record of every node you've already stepped on, what does it mean to arrive at a node that's already in your record?

2Hint 2Explore hint

Store node references (not values) in a hash set. Before moving on, check whether the current node is already in the set.

3Hint 3Explore hint

If the current node is already present, you've looped back — return true. If you walk off the end into null, return false.

A · Core idea

Walk the list one node at a time, recording each node you visit in a hash set of node references. If you ever reach a node that's already in the set, you must have followed next back to somewhere you've been — that's a cycle.

Why store node references, not values. Two different nodes can hold the same val (the list [1, 1] with no cycle is perfectly legal). Hashing on identity — the object reference in Java, id()-style identity via the object itself in Python — guarantees we only flag a true revisit, not a coincidental value match.

Why it terminates. A finite list with no cycle ends at null, so the loop exits and we return false. A list with a cycle has no null, but it has only finitely many distinct nodes, so within n steps we are forced to land on one we've already stored.

Why we still prefer Floyd's. This is correct and easy to explain, but it spends O(n) memory to remember every node. The fast/slow pointer method gets the same answer in O(1) space, which is what an interviewer is usually fishing for once you've shown the baseline.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

head = 3 → 2 → 0 → -4 → (back to 2)

node 3

not seen → add

Stateseen = {3}

Final resulttrue

C · Code with teaching comments

Reference implementation previewpublic class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } }Explore the full code

solution.javaJava

Hash Set — Remember Visited Nodes — reference

3 teaching notes

1
public class ListNode {
2
    int val;
3
    ListNode next;
4
    ListNode(int x) { val = x; next = null; }
5
}
6
 
7
public boolean hasCycle(ListNode head) {
8
    // Stores node references — identity, not value — so coincidental equal values don't
9
    // false-trigger.
10
    Set<ListNode> seen = new HashSet<>();
11
    ListNode curr = head;
12
    while (curr != null) {
13
        // add returns false when the node is already present, i.e. we've looped back.
14
        if (!seen.add(curr)) {
15
            return true;
16
        }
17
        // Advance one node; if curr becomes null the list terminated with no cycle.
18
        curr = curr.next;
19
    }
20
    return false;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

This is the generic 'have I been here before?' membership trick applied to nodes. It's the honest first answer, and naming its O(n) space cost is exactly what motivates the jump to Floyd's.

ComplexityO(n) time, O(n) space — Each node is visited at most once and triggers O(1) average set operations → O(n) time. The set can hold up to n node references → O(n) space.

E · Edge cases and pitfalls3Storing values instead of node references — [1, 1] with no cycle would falsely report true.Explore edge cases

Pitfalls

Storing values instead of node references — [1, 1] with no cycle would falsely report true.
Forgetting the null check in the loop guard and dereferencing past the tail.
Accepting the O(n) space when an O(1) solution exists — say it's a baseline, not the final answer.

03.2

Approach 2 of 2 · Optimal

Floyd's Tortoise & Hare — Fast/Slow Pointers (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'a fast runner laps a slow runner on a circular track'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Picture two runners on a track. If the track is a straight line, the faster runner just reaches the end. What happens on a circular track?

2Hint 2Explore hint

Start slow and fast at the head. Each step move slow by one and fast by two. If they ever point at the same node, there's a cycle.

3Hint 3Explore hint

Guard the fast pointer: only continue while fast and fast.next are non-null, because fast dereferences two links per step. If fast falls off the end, return false.

A · Core idea

Two pointers leave the head together; slow takes single steps, fast takes double steps. On a straight (acyclic) list fast simply runs off the end. On a cyclic list fast is condemned to loop forever and will inevitably catch up to slow from behind.

Why they are guaranteed to meet. Once both pointers are inside the cycle, consider the distance from fast to slow measured forward around the loop. Every step, slow gains 1 and fast gains 2, so that gap shrinks by exactly 1 each step. A quantity that decreases by 1 each step (modulo the cycle length) must eventually hit 0 — meaning they land on the same node. Crucially, because the gap changes by 1, fast can never 'leap over' slow without first matching it.

Why the loop guard is `fast != null && fast.next != null`. fast reads fast.next.next each iteration. If fast is null we'd crash on fast.next; if fast.next is null we'd crash on the second hop. Both conditions being true is exactly what guarantees the double step is safe — and either being false means we hit the end of an acyclic list, so we return false.

Why identity comparison. We test slow == fast on the node references. Comparing slow.val == fast.val is a classic bug: distinct nodes routinely share values, which would report phantom cycles.

Memory win. We replaced the hash set's O(n) bookkeeping with two integer-sized pointers. Same O(n) time, but O(1) space — the upgrade interviewers are listening for.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

head = 3 → 2 → 0 → -4 → (back to 2)

Array state

start

slow=3, fast=3

slow ↓fast ↓

[0]

[1]

[2]

-4

[3]

Current pointerResolved stateNot processed

Final resulttrue

C · Code with teaching comments

solution.javaJava

Floyd's Tortoise & Hare — Fast/Slow Pointers (Optimal) — optimal

4 teaching notes

1
public boolean hasCycle(ListNode head) {
2
    // Tortoise — advances one node per iteration.
3
    ListNode slow = head;
4
    ListNode fast = head;
5
    // Both must be non-null because fast hops two links; failing this means the list
6
    // ended (no cycle).
7
    while (fast != null && fast.next != null) {
8
        slow = slow.next;
9
        // Hare — advances two nodes, so it catches slow from behind inside any cycle.
10
        fast = fast.next.next;
11
        // Reference equality: same node means the hare lapped the tortoise → cycle.
12
        if (slow == fast) {
13
            return true;
14
        }
15
    }
16
    return false;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

Differing speeds convert 'is there a loop?' into 'does the hare lap the tortoise?'. The gap-shrinks-by-one argument is the whole proof, and it generalises: reset one pointer to the head after they meet and you get the cycle's entry node (Linked List Cycle II) for free.

ComplexityO(n) time, O(1) space — No cycle → fast reaches the end in n/2 steps. With a cycle → once both are inside the loop, the gap closes by one per step, so they meet within at most the cycle length. Total work is O(n); only two pointers are stored, so O(1) space.

E · Edge cases and pitfalls6head = null — fast is null on entry, the loop never runs, returns false.Explore edge cases

Edge cases handled

head = nullfast is null on entry, the loop never runs, returns false.
head = [1] with 1.next = 1 (self-loop)fast and fast.next are non-null; after one step slow=1, fast=1 → returns true.
head = [1, 2] no cycleAfter one step fast = null, loop guard fails, returns false.

Pitfalls

Writing fast.next.next without the fast && fast.next guard — null dereference on acyclic lists.
Comparing slow.val == fast.val instead of the references — false positives on repeated values.
Starting fast at head.next as a 'micro-optimization' then mishandling the off-by-one in the meeting condition.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic boolean hasCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Unguarded two-step advance

fast hops two links per iteration, so both fast and fast.next must be non-null. Skipping the guard throws on any list that ends.

Explore the code comparison

Don't write this

while (fast != null) {
    slow = slow.next;
    fast = fast.next.next; // NPE when fast.next is null
    if (slow == fast) return true;
}

Write this instead

while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) return true;
}

Comparing values instead of identity

Different nodes can carry equal values, so a value match does not imply the same node. Use reference/identity comparison.

Explore the code comparison

Don't write this

if slow.val == fast.val:
    return True

Write this instead

if slow is fast:
    return True

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Floyd's fast/slow pointers (tortoise and hare)

Code pattern to memorize

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow is fast: return True
return False

Rules to remember

1Check fast and fast.next before moving — fast advances two, so both must be non-null to avoid a NullPointerException.
2Compare the two pointers by identity (is / == on references), never by value — different nodes can share a value.
3If fast (or fast.next) hits null, the list terminates, so there's definitively no cycle.
4Inside a cycle the gap between fast and slow shrinks by one each step, so they are guaranteed to collide — they can never 'jump over' each other.
5For the start of the cycle (LeetCode 142): after they meet, reset one pointer to head and advance both by one until they meet again.

Use this pattern when

Detect whether a linked list (or implicit 'next' function) loops back on itself
Constant-space cycle detection where a hash set is too memory-hungry
Find a duplicate via index-chasing (Find the Duplicate Number) or cycle entry (Linked List Cycle II)
Happy Number and other 'follow next repeatedly, does it loop?' problems

Choose another pattern when

You also need the set of all visited nodes for something else → a hash set is more useful
Nodes are not uniquely addressable / you only have values → identity comparison won't work, rethink
You need the cycle length or entry immediately → still Floyd's, but with the extra second phase

Interview takeaway

Two pointers at different speeds turn cycle detection from an O(n)-space bookkeeping problem into an O(1)-space race. The same tortoise-and-hare idea reappears in Linked List Cycle II, Find the Duplicate Number, and Happy Number.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternFloyd's fast/slow pointers. The go-to whenever you must detect or locate a cycle in O(1) space — on real linked lists (Cycle / Cycle II) or implicit ones defined by a next-function (Find the Duplicate Number, Happy Number).

Practice queueDirect variations and pattern siblings

Direct follow-ups

Linked List Cycle II
Coming soon
Return the node where the cycle begins: after they meet, reset one pointer to head and step both by one until they meet again.
Find the Duplicate Number
Coming soon
Treat the array as a linked list where i → nums[i]; the duplicate is the cycle entry found via Floyd's.
Happy Number
Coming soon
Follow the digit-square-sum function with slow/fast; a non-happy number falls into a cycle.

Same pattern

←

Reverse Linked List

Continue · Next problem

Merge Two Sorted Lists

easyLinked ListsLC #141Frequently asked

Linked List Cycle Detection

LCPractice

Linked List · 2 of 24 · 8 min

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle if some node can be reached again by continuously following the next pointer. Return true if there is a cycle, otherwise return false. You should not modify the list.

In plain English

Examples

Example 1

Input: head = [3, 2, 0, -4], pos = 1 (tail connects to index 1)
Output: true
Note: The tail node -4 points back to node 2, forming a cycle 2 → 0 → -4 → 2.

Example 2

Input: head = [1, 2], pos = 0
Output: true
Note: The tail node 2 points back to the head, so the two nodes cycle forever.

Example 3

Input: head = [1], pos = -1
Output: false
Note: A single node whose next is null terminates — no cycle.

Constraints

The number of nodes is in the range [0, 10⁴]
-10⁵ ≤ Node.val ≤ 10⁵
The cycle, if present, is created by the tail's next pointing to an earlier node (or to itself)

Clarifying questions4First question: Can a node's next point to itself?Explore questions

Q1.Can a node's next point to itself?
Yes — a single node whose next is itself is a valid one-node cycle and must return true.
Q2.Am I allowed to modify the list (e.g. mark visited nodes)?
I'll treat the list as read-only. Floyd's needs no mutation; marking nodes would corrupt the input and is fragile.
Q3.Do you also need where the cycle begins?
Not for this problem — just true/false. If you did, I'd add Floyd's phase two: reset one pointer to head and walk both one step at a time.
Q4.What about the empty list or a single node with no cycle?
Empty list and a lone node with next = null both return false; the while-loop guard handles them without special-casing.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know the O(1)-space fast/slow trick instead of defaulting to a hash set, and whether you guard the fast pointer's two-step advance against null.

Where candidates slip

Dereferencing fast.next.next without checking fast and fast.next first, or comparing node values instead of node identity.

How to stand out

State the hash-set baseline, then upgrade to Floyd's for O(1) space. Explain *why* they must meet (the gap shrinks by one each step) and mention the cycle-entry extension.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Hash Set — Remember Visited Nodes	`O(n)`	`O(n)`	State it first as the intuitive baseline, then offer Floyd's to save the O(n) space.	Read
2	Floyd's Tortoise & Hare — Fast/Slow Pointers (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'a fast runner laps a slow runner on a circular track'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Hash Set — Remember Visited Nodes

TimeO(n)SpaceO(n)

State it first as the intuitive baseline, then offer Floyd's to save the O(n) space.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you walk the list and keep a record of every node you've already stepped on, what does it mean to arrive at a node that's already in your record?

2Hint 2Explore hint

Store node references (not values) in a hash set. Before moving on, check whether the current node is already in the set.

3Hint 3Explore hint

If the current node is already present, you've looped back — return true. If you walk off the end into null, return false.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

head = 3 → 2 → 0 → -4 → (back to 2)

node 3

not seen → add

Stateseen = {3}

Final resulttrue

C · Code with teaching comments

Reference implementation previewpublic class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } }Explore the full code

solution.javaJava

Hash Set — Remember Visited Nodes — reference

3 teaching notes

1
public class ListNode {
2
    int val;
3
    ListNode next;
4
    ListNode(int x) { val = x; next = null; }
5
}
6
 
7
public boolean hasCycle(ListNode head) {
8
    // Stores node references — identity, not value — so coincidental equal values don't
9
    // false-trigger.
10
    Set<ListNode> seen = new HashSet<>();
11
    ListNode curr = head;
12
    while (curr != null) {
13
        // add returns false when the node is already present, i.e. we've looped back.
14
        if (!seen.add(curr)) {
15
            return true;
16
        }
17
        // Advance one node; if curr becomes null the list terminated with no cycle.
18
        curr = curr.next;
19
    }
20
    return false;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

This is the generic 'have I been here before?' membership trick applied to nodes. It's the honest first answer, and naming its O(n) space cost is exactly what motivates the jump to Floyd's.

ComplexityO(n) time, O(n) space — Each node is visited at most once and triggers O(1) average set operations → O(n) time. The set can hold up to n node references → O(n) space.

E · Edge cases and pitfalls3Storing values instead of node references — [1, 1] with no cycle would falsely report true.Explore edge cases

Pitfalls

Storing values instead of node references — [1, 1] with no cycle would falsely report true.
Forgetting the null check in the loop guard and dereferencing past the tail.
Accepting the O(n) space when an O(1) solution exists — say it's a baseline, not the final answer.

03.2

Approach 2 of 2 · Optimal

Floyd's Tortoise & Hare — Fast/Slow Pointers (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'a fast runner laps a slow runner on a circular track'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Picture two runners on a track. If the track is a straight line, the faster runner just reaches the end. What happens on a circular track?

2Hint 2Explore hint

Start slow and fast at the head. Each step move slow by one and fast by two. If they ever point at the same node, there's a cycle.

3Hint 3Explore hint

Guard the fast pointer: only continue while fast and fast.next are non-null, because fast dereferences two links per step. If fast falls off the end, return false.

A · Core idea

Memory win. We replaced the hash set's O(n) bookkeeping with two integer-sized pointers. Same O(n) time, but O(1) space — the upgrade interviewers are listening for.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

head = 3 → 2 → 0 → -4 → (back to 2)

Array state

start

slow=3, fast=3

slow ↓fast ↓

[0]

[1]

[2]

-4

[3]

Current pointerResolved stateNot processed

Final resulttrue

C · Code with teaching comments

solution.javaJava

Floyd's Tortoise & Hare — Fast/Slow Pointers (Optimal) — optimal

4 teaching notes

1
public boolean hasCycle(ListNode head) {
2
    // Tortoise — advances one node per iteration.
3
    ListNode slow = head;
4
    ListNode fast = head;
5
    // Both must be non-null because fast hops two links; failing this means the list
6
    // ended (no cycle).
7
    while (fast != null && fast.next != null) {
8
        slow = slow.next;
9
        // Hare — advances two nodes, so it catches slow from behind inside any cycle.
10
        fast = fast.next.next;
11
        // Reference equality: same node means the hare lapped the tortoise → cycle.
12
        if (slow == fast) {
13
            return true;
14
        }
15
    }
16
    return false;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6head = null — fast is null on entry, the loop never runs, returns false.Explore edge cases

Edge cases handled

head = nullfast is null on entry, the loop never runs, returns false.
head = [1] with 1.next = 1 (self-loop)fast and fast.next are non-null; after one step slow=1, fast=1 → returns true.
head = [1, 2] no cycleAfter one step fast = null, loop guard fails, returns false.

Pitfalls

Writing fast.next.next without the fast && fast.next guard — null dereference on acyclic lists.
Comparing slow.val == fast.val instead of the references — false positives on repeated values.
Starting fast at head.next as a 'micro-optimization' then mishandling the off-by-one in the meeting condition.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic boolean hasCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Unguarded two-step advance

fast hops two links per iteration, so both fast and fast.next must be non-null. Skipping the guard throws on any list that ends.

Explore the code comparison

Don't write this

while (fast != null) {
    slow = slow.next;
    fast = fast.next.next; // NPE when fast.next is null
    if (slow == fast) return true;
}

Write this instead

while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) return true;
}

Comparing values instead of identity

Different nodes can carry equal values, so a value match does not imply the same node. Use reference/identity comparison.

Explore the code comparison

Don't write this

if slow.val == fast.val:
    return True

Write this instead

if slow is fast:
    return True

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Floyd's fast/slow pointers (tortoise and hare)

Code pattern to memorize

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow is fast: return True
return False

Rules to remember

1Check fast and fast.next before moving — fast advances two, so both must be non-null to avoid a NullPointerException.
2Compare the two pointers by identity (is / == on references), never by value — different nodes can share a value.
3If fast (or fast.next) hits null, the list terminates, so there's definitively no cycle.
4Inside a cycle the gap between fast and slow shrinks by one each step, so they are guaranteed to collide — they can never 'jump over' each other.
5For the start of the cycle (LeetCode 142): after they meet, reset one pointer to head and advance both by one until they meet again.

Use this pattern when

Detect whether a linked list (or implicit 'next' function) loops back on itself
Constant-space cycle detection where a hash set is too memory-hungry
Find a duplicate via index-chasing (Find the Duplicate Number) or cycle entry (Linked List Cycle II)
Happy Number and other 'follow next repeatedly, does it loop?' problems

Choose another pattern when

You also need the set of all visited nodes for something else → a hash set is more useful
Nodes are not uniquely addressable / you only have values → identity comparison won't work, rethink
You need the cycle length or entry immediately → still Floyd's, but with the extra second phase

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Linked List Cycle II
Coming soon
Return the node where the cycle begins: after they meet, reset one pointer to head and step both by one until they meet again.
Find the Duplicate Number
Coming soon
Treat the array as a linked list where i → nums[i]; the duplicate is the cycle entry found via Floyd's.
Happy Number
Coming soon
Follow the digit-square-sum function with slow/fast; a non-happy number falls into a cycle.

Same pattern

←

Reverse Linked List

Continue · Next problem

Merge Two Sorted Lists