Detect a Cycle in a Linked List in Java
Problem
A linked list has a cycle when some node's next pointer leads back to an earlier node, so walking the list never reaches the end.
Given the head of a singly linked list, decide whether it contains a cycle and, if it does, find the node where the cycle starts.
Java Program
public class DetectCycleLinkedList {
static class Node {
int value;
Node next;
Node(int value) {
this.value = value;
}
}
// Floyd's algorithm: returns the node where the cycle starts, or null if there is none
static Node findCycleStart(Node head) {
Node slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // one step
fast = fast.next.next; // two steps
if (slow == fast) { // they met inside the cycle
Node p = head;
while (p != slow) { // move both one step at a time; they meet at the entry
p = p.next;
slow = slow.next;
}
return p;
}
}
return null; // fast reached the end, so the list has an end
}
static Node buildList(int count) {
Node head = new Node(1), tail = head;
for (int v = 2; v <= count; v++) {
tail.next = new Node(v);
tail = tail.next;
}
return head;
}
public static void main(String[] args) {
Node straight = buildList(6);
System.out.println("List 1 has a cycle: " + (findCycleStart(straight) != null));
Node looped = buildList(6);
Node third = looped.next.next;
Node last = third.next.next.next;
last.next = third; // 6 points back to 3
Node start = findCycleStart(looped);
System.out.println("List 2 has a cycle: " + (start != null));
System.out.println("Cycle starts at node: " + start.value);
}
}Output
Core Logic
A slow pointer moves one step and a fast pointer two; if there's a cycle the fast one eventually laps the slow one inside it, and if not, the fast one falls off the end.
- 1Both pointers start at the head.
- 2The loop advances them until
fastorfast.nextis null (no cycle) or they land on the same node (cycle). - 3After they meet, a new pointer starts from the head while
slowkeeps going, both one step at a time. - 4The node where those two meet is the start of the cycle.
Key Point: The pointers must be compared with == (same node), not by value — two different nodes can hold equal values.
Why: The fast pointer catches up within a number of steps proportional to the list length, and only two or three references are used.
Key Concepts
Approach 2: Using a HashSet
import java.util.HashSet;
import java.util.Set;
public class DetectCycleHashSet {
static class Node {
int value;
Node next;
Node(int value) {
this.value = value;
}
}
public static void main(String[] args) {
Node head = new Node(1);
Node tail = head;
for (int v = 2; v <= 6; v++) {
tail.next = new Node(v);
tail = tail.next;
}
tail.next = head.next.next; // 6 points back to 3
Set<Node> seen = new HashSet<>(); // node identity, not value
Node current = head;
while (current != null && seen.add(current)) { // add() returns false for a repeat
current = current.next;
}
if (current == null) {
System.out.println("No cycle");
} else {
System.out.println("Cycle starts at node: " + current.value);
System.out.println("Nodes visited before the repeat: " + seen.size());
}
}
}
Output
Core Logic
Remembering every node already visited makes a cycle obvious: the first node seen twice is where the loop begins.
- 1The list is walked from the head.
- 2
seen.add(current)returnsfalsewhen the node is already in the set. - 3Reaching
nullmeans the list ends, so there is no cycle. - 4Otherwise
currentis the first repeated node — the start of the cycle.
Key Point: Simple and easy to explain, but it stores every node — Floyd's algorithm gives the same answer with constant extra memory, which is what interviewers usually push for.
Why: Each node is visited once and stored in the set.
Key Concepts
Interview Questions
How do you find the length of the cycle?
After the slow and fast pointers meet, keep one still and move the other until it returns, counting the steps.
How do you remove the cycle?
Find the node where the cycle starts, then walk around the loop to the node whose next points back to it, and set that next to null.