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.
public int val;
public ListNode next;
public ListNode(int x) {
val = x;
next = null;
}
}
public class Solution {
public ListNode DetectCycle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
fast = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}The C# solution utilizes Floyd's Cycle Detection method by manipulating instances of ListNode within the DetectCycle function. This finds a meeting point within the cycle, if it exists, then determines the entry point by resetting one of the pointers back to the head of the list.
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#include <stdio.h>
2#include <stdlib.h>
3
4#define TABLE_SIZE 10000
5
6typedef struct ListNode {
7 int val;
8 struct ListNode *next;
9} ListNode;
10
11struct ListNode **createTable() {
12 struct ListNode **table = (struct ListNode **)calloc(TABLE_SIZE, sizeof(struct ListNode *));
13 return table;
14}
15
16int hash(struct ListNode *node) {
17 return ((unsigned long)node >> 3) % TABLE_SIZE;
18}
19
20int searchInsert(struct ListNode **table, struct ListNode *node) {
21 int index = hash(node);
22 struct ListNode *current = table[index];
23 while (current) {
24 if (current == node) return 1;
25 current = current->next;
26 }
27 // Insert at the beginning of the chain
28 struct ListNode *newNode = malloc(sizeof(struct ListNode));
29 newNode->val = node->val;
30 newNode->next = table[index];
31 table[index] = newNode;
32 return 0;
33}
34
35struct ListNode *detectCycle(struct ListNode *head) {
36 struct ListNode **table = createTable();
37 struct ListNode *current = head;
38 while (current) {
39 if (searchInsert(table, current)) {
40 return current; // Start of the cycle
41 }
42 current = current->next;
43 }
44 return NULL; // No cycle detected
45}This C solution creates a hash table, inserting each visited node with a hashed pointer as the key. If a node is found in the table during traversal, it's part of the cycle's start and returned. Otherwise, the list is acyclic.