Linked List Cycle — Floyd’s Tortoise and Hare
Run two pointers at different speeds; if a cycle exists they eventually collide without any extra memory.
Problem Statement
Determine whether a singly linked list contains a cycle.
Why This Problem Matters
- Cycle detection is a foundational pointer manipulation skill for linked structures.
- Space-free detection often surfaces in interviews as a follow-up to hash-set solutions.
- Understanding the proof of Floyd’s algorithm prepares you for finding the cycle start later.
Thought Process
Consider the naive approach
A hash set of visited nodes works but costs O(n) space, which the follow-up forbids.
Leverage different speeds
If one pointer moves twice as fast as the other, it laps the slower pointer inside a cycle.
Guard against null pointers
Always check fast and fast.next before advancing to avoid NullPointerException.
Step-by-Step Reasoning
- Handle empty or single-node lists by returning false immediately.
- Initialise slow and fast pointers to head.
- Advance slow by one and fast by two until fast hits null (no cycle) or they meet (cycle).
- Return true when slow == fast; otherwise false after the loop.
Dry Run
List: 1 → 2 → 3 → 4 → 2 ...
slow visits nodes 1,2,3; fast visits 1,3,2 and collides with slow at node 3.
List: 1 → 2 → null
fast.next becomes null; loop exits and returns false.
Complexity Analysis
Time
O(n)
Space
O(1)
Why
Each pointer runs through the list at most once and uses constant extra space.
Annotated Solution
public class LinkedListCycle {
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
private static class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
}Two pointers moving at different speeds guarantee a collision iff a cycle exists, delivering O(1) space detection.
Common Pitfalls
- Comparing node values instead of references fails when duplicates appear.
- Not checking fast.next before fast.next.next dereferences null.
- Returning true the moment fast becomes null misinterprets the stopping condition.
Follow-Up Questions
- Can you find the node where the cycle begins after detecting it?
- How would you modify the algorithm for doubly linked lists?