This is a classical problem solved most optimally using the Bellman-Ford Cycle Detection algorithm a.k.a. Tortoise Hair approach. The algorithm is as follows:
- Traverse the Linked List using two pointers “slow” and “fast”
- Move the slow pointer by 1 and the fast pointer by 2
- If these pointers meet at some node then there is a cycle else there is no cycle.
The proof is pretty interesting and can be found on StackExchance.
class Solution {
public:
bool hasCycle(ListNode *head) {
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;
}
};
Time complexity: O(n)