The Floyd's Tortoise and Hare algorithm is a two-pointer technique that is used to detect cycles in a linked list. The approach involves using two pointers, one moving twice as fast as the other. If there's a cycle, the fast pointer will eventually meet the slow pointer. This method works in O(n) time with O(1) space.
Time Complexity: O(n), where n is the number of nodes in the list.
Space Complexity: O(1), constant space usage.
1#include <stdbool.h>
2
3struct ListNode {
4 int val;
5 struct ListNode *next;
6};
7
8bool hasCycle(struct ListNode *head) {
9 struct ListNode *slow = head, *fast = head;
10 while (fast != NULL && fast->next != NULL) {
11 slow = slow->next;
12 fast = fast->next->next;
13 if (slow == fast) {
14 return true;
15 }
16 }
17 return false;
18}In this solution, we create two pointers, slow and fast. The slow pointer moves one step at a time while the fast moves two steps. If the list contains a cycle, these pointers will eventually meet inside the cycle. If there's no cycle, fast or fast->next will become null.
This approach uses a HashSet to track the nodes visited during the traversal. If a node is encountered twice, there is a cycle. This method requires O(n) space but is simpler to understand.
Time Complexity: O(n^2) because of nested loops (non-optimal use of memory).
Space Complexity: O(n), where n is the number of nodes (uses additional storage).
1#include <unordered_set>
2using namespace std;
3
4struct ListNode {
5 int val;
6 ListNode *next;
7 ListNode(int x) : val(x), next(NULL) {}
8};
9
10class Solution {
11public:
12 bool hasCycle(ListNode *head) {
13 unordered_set<ListNode*> visited;
14 while (head != nullptr) {
15 if (visited.find(head) != visited.end()) return true;
16 visited.insert(head);
17 head = head->next;
18 }
19 return false;
20 }
21};The C++ solution uses an unordered_set for efficient cycle detection. This set tracks nodes and determines if a node is revisited.