Approach Summary
Floyd's tortoise and hare: slow moves 1, fast moves 2. If they meet, there is a cycle.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Hash Set Visited Tracking | O(n) | O(n) | Record visited nodes in a set; return true if a node is encountered a second time. |
| 2 Approach 2: Floyd's Tortoise and Hare (Optimal) | O(n) | O(1) | Fast pointer moves 2 steps, slow moves 1 step; if they meet, a cycle exists. |
Step 1: Baseline
Approach 1: Hash Set Visited Tracking
Time: O(n)
Space: O(n)
Maintain a hash set of node pointers. Traverse the list node by node. If the current node is already in the set, a cycle has been detected. Otherwise, insert it and continue until reaching null.
Approach 1: Hash Set Visited Tracking Implementation
Approach 1: Hash Set Visited Tracking
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> visited = new HashSet<>();
ListNode curr = head;
while (curr != null) {
if (visited.contains(curr)) return true;
visited.add(curr);
curr = curr.next;
}
return false;
}
}class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_set<ListNode*> visited;
ListNode* curr = head;
while (curr != NULL) {
if (visited.find(curr) != visited.end()) return true;
visited.insert(curr);
curr = curr->next;
}
return false;
}
};class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
visited = set()
curr = head
while curr:
if curr in visited:
return True
visited.add(curr)
curr = curr.next
return Falsefunction hasCycle(head) {
const visited = new Set();
let curr = head;
while (curr !== null) {
if (visited.has(curr)) return true;
visited.add(curr);
curr = curr.next;
}
return false;
} Step 2: Most Optimized
Approach 2: Floyd's Tortoise and Hare (Optimal)
Time: O(n)
Space: O(1)
By moving fast at twice the speed of slow, each step reduces the distance between fast and slow by 1 inside any cycle. Because the distance decreases by 1 modulo cycle length on each step, fast must collide with slow without ever jumping over it.
Approach 2: Floyd's Tortoise and Hare (Optimal) Implementation
Approach 2: Floyd's Tortoise and Hare (Optimal)
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null) return false;
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;
}
}class Solution {
public:
bool hasCycle(ListNode *head) {
if (!head) return false;
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
};class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return Falsefunction hasCycle(head) {
if (!head) return false;
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}Edge Cases to Watch
- Empty list (head is null; returns false)
- Single node with no cycle (node.next is null; returns false)
- Single node pointing to itself (node.next is node; returns true)
- Two nodes forming a cycle (1 -> 2 -> 1; returns true)
Algorithmic Pattern
View Pattern Guide →
Master the Linked List Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Linked List pattern.
Framework: Linked List • Interview Prep: Tested at FAANG •
Explore all Linked List problems & invariants →
How to Recognize This Pattern
- Detect cycle in linked list
- O(1) space required
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Tags
Linked List Two Pointers Hash Table
Frequently Asked Questions
What is the optimal time and space complexity for Linked List Cycle?
The optimal solution for Linked List Cycle achieves O(n) runtime complexity and requires O(1) auxiliary space. Time complexity is O(n). In the presence of a cycle of length C, the fast pointer catches the slow pointer within at most C iterations once slow enters the cycle. Space complexity is O(1) auxiliary space as only two node pointers are used.
How do I identify that Linked List Cycle requires the Linked List pattern?
In technical interviews, look for key problem signals: Detect cycle in linked list; O(1) space required. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Linked List strategy.
What critical edge cases must be handled in Linked List Cycle?
Essential edge cases to verify include: Empty list (head is null; returns false); Single node with no cycle (node.next is null; returns false); Single node pointing to itself (node.next is node; returns true); Two nodes forming a cycle (1 -> 2 -> 1; returns true). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Linked List Cycle?
Linked List Cycle is a Easy-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Microsoft, Google.