Sponsored
Sponsored
The Floyd's Cycle Detection Algorithm, also known as the tortoise and hare algorithm, is well-suited for detecting cycles in a linked list.
In this approach, two pointers (slow and fast) are initiated. The slow pointer moves one step at a time, while the fast pointer moves two steps. If a cycle is present, the fast pointer will meet the slow pointer within the cycle. Once a cycle is detected, reset one pointer to the head of the linked list and keep the other pointer at the meeting point. Move both pointers one step at a time; the node where they meet again is the cycle's start.
Time Complexity: O(n) - The list is traversed twice at most.
Space Complexity: O(1) - No additional space apart from pointers.
1#include <stdio.h>
2#include <stdlib.h>
3
4// Definition for singly-linked list.
5struct ListNode {
6 int val;
7 struct ListNode *next;
8};
9
10struct ListNode *detectCycle(struct ListNode *head) {
11 if (head == NULL || head->next == NULL) return NULL;
12 struct ListNode *slow = head, *fast = head;
13 while (fast != NULL && fast->next != NULL) {
14 slow = slow->next;
15 fast = fast->next->next;
16 if (slow == fast) { // Cycle detected
17 fast = head;
18 while (slow != fast) {
19 slow = slow->next;
20 fast = fast->next;
21 }
22 return slow; // start of the cycle
23 }
24 }
25 return NULL; // no cycle
26}The C implementation sets up a tortoise (slow) and a hare (fast) pointer. In a loop, it increments each one according to their respective speeds. If a collision between slow and fast occurs, a cycle is detected. The fast pointer is then set to the head of the list, and both slow and fast point to the next pointers. When they meet again, the node is returned as the starting point of the cycle.
This approach involves using a hash table (or set) to record visited nodes. Traverse the linked list, and for each node, check if it has already been seen (exists in the hash set). If it has, a cycle is detected that starts at this node. If the end of the list is reached without seeing any node twice, the list does not contain a cycle.
Though this technique uses extra space for the data structure, it can be easier to implement and understand.
Time Complexity: O(n) - each node is visited once.
Space Complexity: O(n) - for the hash table.
1
In the Java implementation, a HashSet maintains record of previously seen nodes. The function traverses every node. If HashSet already contains it, cycle detected; otherwise, the node is added.