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 <iostream>
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 ListNode *slow = head, *fast = head;
14 while (fast && fast->next) {
15 slow = slow->next;
16 fast = fast->next->next;
17 if (slow == fast) return true;
18 }
19 return false;
20 }
21};This C++ implementation follows the same logic as the C solution, but using a class structure to encapsulate the method. The ListNode structure is used for the linked list nodes.
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 <stdbool.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode *next;
7};
8
9bool hasCycle(struct ListNode *head) {
10 struct ListNode **nodes = malloc(10000 * sizeof(struct ListNode*));
11 int idx = 0;
12 while (head != NULL) {
13 for (int i = 0; i < idx; i++) {
14 if (nodes[i] == head) {
15 free(nodes);
16 return true;
17 }
18 }
19 nodes[idx++] = head;
20 head = head->next;
21 }
22 free(nodes);
23 return false;
24}This C solution simulates a HashSet using an array to record visited nodes. By checking existing entries, it detects cycles but uses O(n) space.