Loading…

mediumLinked ListsAsked very often

Detect a Cycle in a Linked List

Q: How do you solve Detect a Cycle in a Linked List using the Hash Set — Remember Visited Nodes (Baseline) approach?

When to use it: Mention first as the obvious answer, then improve the space with fast/slow pointers. We walk the list and remember every node we've stood on; revisiting one means we've looped. **Why store nodes, not values.** A cycle is a structural fact — some `next` points back to an earlier *node*. Storing values would misfire on lists with repeated numbers. The set holds node references (identity). **The two ways the walk ends.** Either we step onto a node already in the set (we've come around a loop → return true), or we reach null (the list terminated → return false). Exactly one happens, so the algorithm always halts. **Why we improve on it.** This is the most direct solution and easy to defend, but it spends O(n) memory. Floyd's pointers get the same answer in O(1) space, which is the usual target — so present this, then optimize. Time complexity: O(n). Space complexity: O(n).

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

When to use it: The O(1)-space answer they want. Name it 'tortoise and hare' and explain why the pointers must meet inside a loop. We send a slow pointer (one step) and a fast pointer (two steps) from the head; a collision proves a cycle, and fast running off the end proves there isn't one. **Why they must meet inside a cycle.** Once both pointers are inside the loop, consider the gap from fast to slow measured *forward around the ring*. Each step, slow advances 1 and fast advances 2, so fast gains exactly 1 on slow every step. A gap that shrinks by 1 each step inside a finite ring must hit 0 — and because it shrinks by exactly 1 (not 2 or more), fast can't leap over slow without landing on it. So they collide. This is why fast moves 2 and not 3: a larger stride could skip past slow on a small loop. **Why no cycle terminates safely.** If the list ends, fast (the faster pointer) reaches null first. The loop condition `fast != null && fast.next != null` catches both the odd-length case (fast becomes null) and the even-length case (fast.next becomes null) before we ever dereference. Exit the loop → return false. **The null-guard trap.** The single most common bug is `fast = fast.next.next` without first checking that `fast` and `fast.next` are non-null. On an acyclic list — or any list with an even node count — `fast.next` becomes null and `fast.next.next` throws. Both guards are mandatory, in that order (short-circuit). **Compare by identity, and move before comparing.** The collision test is `slow == fast` on references. Also advance *then* compare: if you compare first, slow and fast both start at head and you'd wrongly report a cycle on step zero. Time complexity: O(n). Space complexity: O(1).

Linked List · 19 of 24 · 9 min

You are given the head of a singly linked list. A cycle exists if some node's next points back to an earlier node, so following next repeats forever.

Return true if the list contains a cycle, and false otherwise. Do not modify the list.

In plain English

Each node has exactly one next pointer, so following next either ends at null (no cycle) or loops forever inside a ring of nodes (cycle). We must decide which, without altering the list and ideally without extra memory.

Examples

Example 1

Input: list = [3, 2, 0, -4], tail.next → node at index 1
Output: true
Note: The last node points back to the node holding 2, forming a loop, so the pointers eventually meet.

Example 2

Input: list = [1, 2], tail.next → head
Output: true
Note: Two nodes pointing in a ring; fast laps slow and they collide.

Example 3

Input: list = [1], tail.next → null
Output: false
Note: Single node ending in null — fast.next is null, the loop exits, no cycle.

Constraints

0 ≤ number of nodes ≤ 10⁴
-10⁵ ≤ Node.val ≤ 10⁵
The cycle, if present, can start at any node (including the head)
Must run in O(1) extra space for the optimal solution

Clarifying questions4First question: Is the cycle defined by a node pointing back, or by repeated values?Explore questions

Q1.Is the cycle defined by a node pointing back, or by repeated values?
By a node's next pointing to an earlier node — structural identity. Repeated values do not imply a cycle, so I compare node references.
Q2.Can I use extra memory, or is O(1) space required?
I'll show the O(n)-space hash-set approach for clarity, then the O(1)-space fast/slow pointers, which is usually what's wanted.
Q3.Am I allowed to modify the list (e.g. mark visited nodes)?
No — keep it read-only. Mutation-based marking would corrupt the input.
Q4.Do I need to return the cycle's starting node?
Here we only return true/false. Finding the entry node is a known follow-up (Floyd's second phase).

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 laps slow and they land on the same node — return true. If fast (or fast.next) reaches null, the list ends, so there's no cycle. O(n) time, O(1) space — no hash set needed.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know Floyd's fast/slow pointers, can argue why they must meet inside a cycle, and whether you null-guard fast.next before the double advance.

Where candidates slip

Advancing fast = fast.next.next without first checking fast and fast.next for null, causing a NullPointerException on lists with no cycle or an even number of nodes.

How to stand out

State the O(1)-space fast/slow solution, explain the 'fast gains one node per step on slow so it must close any gap inside the loop' argument, and mention the hash-set baseline plus the cycle-start follow-up (Floyd's phase 2).

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 (Baseline)	`O(n)`	`O(n)`	Mention first as the obvious answer, then improve the space with fast/slow pointers.	Read
2	Floyd's Fast/Slow Pointers — Tortoise and Hare (Optimal)Optimal	`O(n)`	`O(1)`	The O(1)-space answer they want. Name it 'tortoise and hare' and explain why the pointers must meet inside a loop.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewDetect a cycle in a linked listO(1) space required?YesNoExplore 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 (Baseline)

TimeO(n)SpaceO(n)

Mention first as the obvious answer, then improve the space with fast/slow pointers.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

How would you notice you've arrived at a node you've already stood on?

2Hint 2Explore hint

Store each node's identity as you walk. What does it mean if next leads to a node already stored?

3Hint 3Explore hint

If you reach null before re-seeing a node, the list is finite — no cycle.

A · Core idea

We walk the list and remember every node we've stood on; revisiting one means we've looped.

Why store nodes, not values. A cycle is a structural fact — some next points back to an earlier node. Storing values would misfire on lists with repeated numbers. The set holds node references (identity).

The two ways the walk ends. Either we step onto a node already in the set (we've come around a loop → return true), or we reach null (the list terminated → return false). Exactly one happens, so the algorithm always halts.

Why we improve on it. This is the most direct solution and easy to defend, but it spends O(n) memory. Floyd's pointers get the same answer in O(1) space, which is the usual target — so present this, then optimize.

B · Visual dry run

Interactive dry run

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

list = [1, 2, 3], 3.next → node 2

Hash-map state

visit 1

lookup n1

ValueIndex / state

n1→ •

Continue scanning

insert n1

Final resulttrue

C · Code with teaching comments

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

solution.javaJava

Hash Set — Remember Visited Nodes (Baseline) — reference

3 teaching notes

1
public class ListNode {
2
    int val;
3
    ListNode next;
4
    ListNode() {}
5
    ListNode(int val) { this.val = val; }
6
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
7
}
8
 
9
public boolean hasCycle(ListNode head) {
10
    // Holds visited node references — identity, not value.
11
    Set<ListNode> seen = new HashSet<>();
12
    for (ListNode cur = head; cur != null; cur = cur.next) {
13
        // add returns false if cur was already present → we've looped back.
14
        if (!seen.add(cur)) {
15
            return true;
16
        }
17
    }
18
    // Reached null without a repeat → finite list, no cycle.
19
    return false;
20
}

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

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

Cycle detection becomes 'have I seen this exact node before?' — the same remember-and-probe membership idea as Two Sum, applied to references.

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

E · Edge cases and pitfalls5list = [] — head is null; loop never runs → false.Explore edge cases

Edge cases handled

list = []head is null; loop never runs → false.
list = [1], no cycleAdd n1, advance to null → false.

Pitfalls

Storing values instead of node references — false positives on repeated values.
Adding cur after the check but forgetting to advance cur — infinite loop on acyclic lists.
Treating O(n) space as acceptable when the interviewer wants O(1).

03.2

Approach 2 of 2 · Optimal

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

TimeO(n)SpaceO(1)

The O(1)-space answer they want. Name it 'tortoise and hare' and explain why the pointers must meet inside a loop.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Imagine two runners on a track, one twice as fast. On a circular track, what eventually happens to the gap between them?

2Hint 2Explore hint

Move slow one node and fast two nodes each step. Inside a cycle, fast closes the gap to slow by exactly one node per step — so it can't jump over without landing on it.

3Hint 3Explore hint

If there's no cycle, fast runs off the end. What two things must you null-check before doing fast = fast.next.next?

A · Core idea

We send a slow pointer (one step) and a fast pointer (two steps) from the head; a collision proves a cycle, and fast running off the end proves there isn't one.

Why they must meet inside a cycle. Once both pointers are inside the loop, consider the gap from fast to slow measured forward around the ring. Each step, slow advances 1 and fast advances 2, so fast gains exactly 1 on slow every step. A gap that shrinks by 1 each step inside a finite ring must hit 0 — and because it shrinks by exactly 1 (not 2 or more), fast can't leap over slow without landing on it. So they collide. This is why fast moves 2 and not 3: a larger stride could skip past slow on a small loop.

Why no cycle terminates safely. If the list ends, fast (the faster pointer) reaches null first. The loop condition fast != null && fast.next != null catches both the odd-length case (fast becomes null) and the even-length case (fast.next becomes null) before we ever dereference. Exit the loop → return false.

The null-guard trap. The single most common bug is fast = fast.next.next without first checking that fast and fast.next are non-null. On an acyclic list — or any list with an even node count — fast.next becomes null and fast.next.next throws. Both guards are mandatory, in that order (short-circuit).

Compare by identity, and move before comparing. The collision test is slow == fast on references. Also advance then compare: if you compare first, slow and fast both start at head and you'd wrongly report a cycle on step zero.

B · Visual dry run

Interactive dry run

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

list = [1, 2, 3, 4], 4.next → node 2 (cycle of length 3)

Interactive diagram

Hare gains one node per step on the tortoise

init

Active call / nodeSupporting contextReturned stateNot active

Inside the loop the forward gap shrinks by exactly 1 each step, so the hare must land on the tortoise.

Final resulttrue

C · Code with teaching comments

solution.javaJava

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

5 teaching notes

1
public boolean hasCycle(ListNode head) {
2
    ListNode slow = head;
3
    ListNode fast = head;
4
    // Guard BOTH fast and fast.next before the double hop — the named null trap.
5
    while (fast != null && fast.next != null) {
6
        // Tortoise advances one node.
7
        slow = slow.next;
8
        // Hare advances two; safe only because of the guards above.
9
        fast = fast.next.next;
10
        // Identity match means they've collided inside a cycle.
11
        if (slow == fast) {
12
            return true;
13
        }
14
    }
15
    // Loop exited because fast hit the end → no cycle.
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

Different speeds turn 'is there a loop?' into 'do two walkers collide?'. Because fast gains exactly one node per step, no gap inside a cycle can survive — the collision is guaranteed, and the finite list lets fast escape to null. The named trap is the missing fast.next null-check before the double hop.

ComplexityO(n) time, O(1) space — Without a cycle, fast reaches the end in n/2 steps. With a cycle of length L, once slow enters the loop fast catches it within L steps. Total O(n). Only two pointers → O(1) space.

E · Edge cases and pitfalls7list = [] — fast is null; loop condition false immediately → false.Explore edge cases

Edge cases handled

list = []fast is null; loop condition false immediately → false.
list = [1, 2] no cycleslow→2, fast→2.next.next: fast.next is null after one step → loop exits → false.
list = [1], 1.next → 1 (self-loop)slow→1, fast→1 (1.next.next = 1) → slow is fast → true.

Pitfalls

Writing fast = fast.next.next without guarding fast and fast.next — null dereference on acyclic or even-length lists.
Comparing slow == fast before advancing — false 'cycle' on the very first check since both start at head.
Comparing values instead of node identity.
Moving fast by 3 (or more) instead of 2 — it can leap over slow on a small loop and miss the collision.

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.

Skipping the fast.next null guard

Advancing fast two steps requires both fast and fast.next to exist. On an acyclic list (or any even-length one) fast.next becomes null, and fast.next.next throws a null dereference.

Explore the code comparison

Don't write this

while (fast != null) {        // missing fast.next check
    slow = slow.next;
    fast = fast.next.next;    // NPE when fast.next is null
}

Write this instead

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

Comparing before moving

Both pointers start at head, so an equality check before the first move is trivially true and reports a cycle on a list that has none.

Explore the code comparison

Don't write this

while fast and fast.next:
    if slow is fast:        # true on entry — false positive
        return True
    slow = slow.next
    fast = fast.next.next

Write this instead

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

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

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

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

1Guard both fast and fast.next before advancing fast two steps — skip either and you null-dereference (the named trap).
2Move slow by 1 and fast by 2, then compare. Comparing before moving makes them 'equal' at the start and falsely reports a cycle.
3Compare by identity (slow is fast), never by value — repeated values aren't a loop.
4If the loop exits via the while condition, fast hit the end → no cycle, return false.
5Do not modify the list (no marking visited via mutation) — it must stay read-only.

Use this pattern when

Decide whether a linked list loops back on itself
O(1) extra space is required, ruling out a hash set
Finding a cycle's start, its length, or the middle of a list (same fast/slow skeleton)
Cycle detection in any 'functional graph' where each node has one successor

Choose another pattern when

You also need every visited node recorded for other reasons → a hash set may be reused
Nodes carry no stable identity (e.g. value-copied) → identity comparison won't work
The structure has multiple out-edges per node → this is a general graph; use DFS/visited colors
You may freely mutate and prefer the simplest code → marking visited can be acceptable

Interview takeaway

Two pointers at different speeds will always collide inside a loop and always exit a finite list — that single idea detects cycles in O(1) space. The same tortoise-and-hare skeleton finds the cycle's entry, the list's middle, and duplicates in Find the Duplicate Number.

Continue

Transfer the pattern to another problem

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

Transferable patternFloyd's tortoise-and-hare: two pointers at different speeds collide inside any cycle and escape any finite list, all in O(1) space. The same skeleton finds the cycle's entry, the list's middle, and duplicates in a functional graph.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Linked List Cycle II
After the collision, reset one pointer to head and advance both by one — they meet at the cycle's entry.
Middle of the Linked List
Same fast/slow skeleton: when fast reaches the end, slow sits on the middle.
Find the Duplicate Number
Coming soon
Treat the array as a functional graph and run Floyd's cycle detection to find the repeated value.

Same pattern

←

Insert a Node at a Specific Position in a Linked List

Continue · Next problem

Merge Two Sorted Linked Lists

mediumLinked ListsAsked very often

Detect a Cycle in a Linked List

Linked List · 19 of 24 · 9 min

You are given the head of a singly linked list. A cycle exists if some node's next points back to an earlier node, so following next repeats forever.

Return true if the list contains a cycle, and false otherwise. Do not modify the list.

In plain English

Examples

Example 1

Input: list = [3, 2, 0, -4], tail.next → node at index 1
Output: true
Note: The last node points back to the node holding 2, forming a loop, so the pointers eventually meet.

Example 2

Input: list = [1, 2], tail.next → head
Output: true
Note: Two nodes pointing in a ring; fast laps slow and they collide.

Example 3

Input: list = [1], tail.next → null
Output: false
Note: Single node ending in null — fast.next is null, the loop exits, no cycle.

Constraints

0 ≤ number of nodes ≤ 10⁴
-10⁵ ≤ Node.val ≤ 10⁵
The cycle, if present, can start at any node (including the head)
Must run in O(1) extra space for the optimal solution

Clarifying questions4First question: Is the cycle defined by a node pointing back, or by repeated values?Explore questions

Q1.Is the cycle defined by a node pointing back, or by repeated values?
By a node's next pointing to an earlier node — structural identity. Repeated values do not imply a cycle, so I compare node references.
Q2.Can I use extra memory, or is O(1) space required?
I'll show the O(n)-space hash-set approach for clarity, then the O(1)-space fast/slow pointers, which is usually what's wanted.
Q3.Am I allowed to modify the list (e.g. mark visited nodes)?
No — keep it read-only. Mutation-based marking would corrupt the input.
Q4.Do I need to return the cycle's starting node?
Here we only return true/false. Finding the entry node is a known follow-up (Floyd's second phase).

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 Floyd's fast/slow pointers, can argue why they must meet inside a cycle, and whether you null-guard fast.next before the double advance.

Where candidates slip

Advancing fast = fast.next.next without first checking fast and fast.next for null, causing a NullPointerException on lists with no cycle or an even number of nodes.

How to stand out

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 (Baseline)	`O(n)`	`O(n)`	Mention first as the obvious answer, then improve the space with fast/slow pointers.	Read
2	Floyd's Fast/Slow Pointers — Tortoise and Hare (Optimal)Optimal	`O(n)`	`O(1)`	The O(1)-space answer they want. Name it 'tortoise and hare' and explain why the pointers must meet inside a loop.	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 (Baseline)

TimeO(n)SpaceO(n)

Mention first as the obvious answer, then improve the space with fast/slow pointers.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

How would you notice you've arrived at a node you've already stood on?

2Hint 2Explore hint

Store each node's identity as you walk. What does it mean if next leads to a node already stored?

3Hint 3Explore hint

If you reach null before re-seeing a node, the list is finite — no cycle.

A · Core idea

We walk the list and remember every node we've stood on; revisiting one means we've looped.

B · Visual dry run

Interactive dry run

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

list = [1, 2, 3], 3.next → node 2

Hash-map state

visit 1

lookup n1

ValueIndex / state

n1→ •

Continue scanning

insert n1

Final resulttrue

C · Code with teaching comments

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

solution.javaJava

Hash Set — Remember Visited Nodes (Baseline) — reference

3 teaching notes

1
public class ListNode {
2
    int val;
3
    ListNode next;
4
    ListNode() {}
5
    ListNode(int val) { this.val = val; }
6
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
7
}
8
 
9
public boolean hasCycle(ListNode head) {
10
    // Holds visited node references — identity, not value.
11
    Set<ListNode> seen = new HashSet<>();
12
    for (ListNode cur = head; cur != null; cur = cur.next) {
13
        // add returns false if cur was already present → we've looped back.
14
        if (!seen.add(cur)) {
15
            return true;
16
        }
17
    }
18
    // Reached null without a repeat → finite list, no cycle.
19
    return false;
20
}

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

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

Cycle detection becomes 'have I seen this exact node before?' — the same remember-and-probe membership idea as Two Sum, applied to references.

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

E · Edge cases and pitfalls5list = [] — head is null; loop never runs → false.Explore edge cases

Edge cases handled

list = []head is null; loop never runs → false.
list = [1], no cycleAdd n1, advance to null → false.

Pitfalls

Storing values instead of node references — false positives on repeated values.
Adding cur after the check but forgetting to advance cur — infinite loop on acyclic lists.
Treating O(n) space as acceptable when the interviewer wants O(1).

03.2

Approach 2 of 2 · Optimal

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

TimeO(n)SpaceO(1)

The O(1)-space answer they want. Name it 'tortoise and hare' and explain why the pointers must meet inside a loop.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Imagine two runners on a track, one twice as fast. On a circular track, what eventually happens to the gap between them?

2Hint 2Explore hint

Move slow one node and fast two nodes each step. Inside a cycle, fast closes the gap to slow by exactly one node per step — so it can't jump over without landing on it.

3Hint 3Explore hint

If there's no cycle, fast runs off the end. What two things must you null-check before doing fast = fast.next.next?

A · Core idea

We send a slow pointer (one step) and a fast pointer (two steps) from the head; a collision proves a cycle, and fast running off the end proves there isn't one.

B · Visual dry run

Interactive dry run

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

list = [1, 2, 3, 4], 4.next → node 2 (cycle of length 3)

Interactive diagram

Hare gains one node per step on the tortoise

init

Active call / nodeSupporting contextReturned stateNot active

Inside the loop the forward gap shrinks by exactly 1 each step, so the hare must land on the tortoise.

Final resulttrue

C · Code with teaching comments

solution.javaJava

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

5 teaching notes

1
public boolean hasCycle(ListNode head) {
2
    ListNode slow = head;
3
    ListNode fast = head;
4
    // Guard BOTH fast and fast.next before the double hop — the named null trap.
5
    while (fast != null && fast.next != null) {
6
        // Tortoise advances one node.
7
        slow = slow.next;
8
        // Hare advances two; safe only because of the guards above.
9
        fast = fast.next.next;
10
        // Identity match means they've collided inside a cycle.
11
        if (slow == fast) {
12
            return true;
13
        }
14
    }
15
    // Loop exited because fast hit the end → no cycle.
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 pitfalls7list = [] — fast is null; loop condition false immediately → false.Explore edge cases

Edge cases handled

list = []fast is null; loop condition false immediately → false.
list = [1, 2] no cycleslow→2, fast→2.next.next: fast.next is null after one step → loop exits → false.
list = [1], 1.next → 1 (self-loop)slow→1, fast→1 (1.next.next = 1) → slow is fast → true.

Pitfalls

Writing fast = fast.next.next without guarding fast and fast.next — null dereference on acyclic or even-length lists.
Comparing slow == fast before advancing — false 'cycle' on the very first check since both start at head.
Comparing values instead of node identity.
Moving fast by 3 (or more) instead of 2 — it can leap over slow on a small loop and miss the collision.

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.

Skipping the fast.next null guard

Advancing fast two steps requires both fast and fast.next to exist. On an acyclic list (or any even-length one) fast.next becomes null, and fast.next.next throws a null dereference.

Explore the code comparison

Don't write this

while (fast != null) {        // missing fast.next check
    slow = slow.next;
    fast = fast.next.next;    // NPE when fast.next is null
}

Write this instead

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

Comparing before moving

Both pointers start at head, so an equality check before the first move is trivially true and reports a cycle on a list that has none.

Explore the code comparison

Don't write this

while fast and fast.next:
    if slow is fast:        # true on entry — false positive
        return True
    slow = slow.next
    fast = fast.next.next

Write this instead

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

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

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

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

1Guard both fast and fast.next before advancing fast two steps — skip either and you null-dereference (the named trap).
2Move slow by 1 and fast by 2, then compare. Comparing before moving makes them 'equal' at the start and falsely reports a cycle.
3Compare by identity (slow is fast), never by value — repeated values aren't a loop.
4If the loop exits via the while condition, fast hit the end → no cycle, return false.
5Do not modify the list (no marking visited via mutation) — it must stay read-only.

Use this pattern when

Decide whether a linked list loops back on itself
O(1) extra space is required, ruling out a hash set
Finding a cycle's start, its length, or the middle of a list (same fast/slow skeleton)
Cycle detection in any 'functional graph' where each node has one successor

Choose another pattern when

You also need every visited node recorded for other reasons → a hash set may be reused
Nodes carry no stable identity (e.g. value-copied) → identity comparison won't work
The structure has multiple out-edges per node → this is a general graph; use DFS/visited colors
You may freely mutate and prefer the simplest code → marking visited can be acceptable

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
After the collision, reset one pointer to head and advance both by one — they meet at the cycle's entry.
Middle of the Linked List
Same fast/slow skeleton: when fast reaches the end, slow sits on the middle.
Find the Duplicate Number
Coming soon
Treat the array as a functional graph and run Floyd's cycle detection to find the repeated value.

Same pattern

←

Insert a Node at a Specific Position in a Linked List

Continue · Next problem

Merge Two Sorted Linked Lists