#141 Linked List Cycle
the problem
In plain words
Given head, return true if some node can be reached again by following next (the list has a cycle), otherwise false.
in head = [3,2,0,-4], pos = 1
out true
The tail links back to the node at index 1.
in head = [1,2], pos = 0
out true
The tail links back to the head.
in head = [1], pos = -1
out false
- 0 ≤ number of nodes ≤ 10⁴
- -10⁵ ≤ Node.val ≤ 10⁵
- pos is -1 or a valid index (it is not passed to your function)
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternFast & slow pointers
A list without a cycle ends in null. With a cycle, a runner moving twice as fast must eventually lap the slow one — like two runners on a circular track.
solutions
From brute force to optimal
Store each node in a HashSet; seeing one twice means a cycle.
- Walk the list.
- If
seen.add(node)returns false → true. - Reaching null → false.
Each node is visited once; set operations are O(1) average.
The set may hold every node.
class Solution { public boolean hasCycle(ListNode head) { Set<ListNode> seen = new HashSet<>(); // identity-based: ListNode does not override equals for (ListNode p = head; p != null; p = p.next) { if (!seen.add(p)) return true; // add() returns false if p was already there } return false; }}slow moves 1, fast moves 2. They meet only if there's a cycle; fast hits null otherwise.
- slow = fast = head.
- While fast and fast.next are not null: slow += 1, fast += 2.
- If slow == fast → true.
- Loop ends → false.
slow enters the cycle within n steps; fast then catches it within one lap.
Two references.
class Solution { public boolean hasCycle(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) return true; } return false; }}Dry run
in the room
How to say it in the interview
talk track
- Start with the HashSet idea in one sentence, then: "Can I do O(1) space? Yes — two pointers at different speeds."
- Explain why they can't miss each other: the gap closes by exactly one per step.
- Compare nodes with
==(identity), never by value — values may repeat.
traps
- Checking
fast.next.nextwithout first checkingfast.next != null. - Starting fast at head.next and then comparing before moving — off-by-one meet logic. Start both at head.
what they ask next
Follow-ups
Return where the cycle starts?
That's LC 142 — after they meet, move a pointer from head and one from the meeting point, one step each; they meet at the entry.
Find the Duplicate Number (LC 287)?
Treat i → nums[i] as a linked list; the duplicate is the entry of the cycle. Same Floyd algorithm, O(1) space (it's below).
before you submit
Edge cases to test
- Empty list → false.
- One node whose
nextis itself → true. - Equal values but no cycle → false: compare nodes, not values.
- The tail points to itself (a loop of length 1).
practise next
Similar problems
- #142Linked List Cycle IIMediumin Linked Lists
- #287Find the Duplicate NumberMediumin Linked Lists
- #202Happy NumberEasyin Math & Numbers