MiddleCodeVery commonNot answered yet
Detect a cycle in a singly-linked list (Floyd's algorithm)
Given the head of a singly-linked list, return true if the list contains a cycle and false otherwise.
Requirements:
advancing the fast pointer (needed for even-length lists).
- O(n) time, O(1) extra space — no auxiliary hash set of visited nodes.
- Guard against null dereference: check both
fastandfast->nextbefore
struct Node {
int val;
Node* next;
};
bool hasCycle(Node* head) {
// your code here
}Write the implementation.
Floyd's tortoise and hare uses two pointers from the head moving at different speeds: slow advances by 1, fast by 2; if they ever meet inside the list a cycle exists, and if fast reaches nullptr the list is acyclic. Time O(n), space O(1).
- ✗Using a hash set to track visited nodes — O(n) space, not needed with Floyd's
- ✗Not checking
fast && fast->nextbefore advancing — leads to null dereference - ✗Stopping on fast == nullptr but not checking fast->next == nullptr (needed for even-length lists)
- →How do you find the start of the cycle after detecting it?
- →How do you find the length of the cycle?
Contents
Task
Detect a cycle in a singly-linked list. Bonus: find the cycle start node.
Solution
bool hasCycle(Node* head) {
Node *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next; fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}Key points
- Floyd's tortoise and hare: O(n) time, O(1) space — optimal.
- To find cycle start: after detection, reset one pointer to head, advance both by 1 until they meet.
Contents
