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.
1public class ListNode {
2 public int val;
3 public ListNode next;
4 public ListNode(int x) {
5 val = x;
6 next = null;
7 }
8}
9
10public class Solution {
11 public bool HasCycle(ListNode head) {
12 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) {
17 return true;
18 }
19 }
20 return false;
21 }
22}The C# implementation mirrors the two-pointer logic found in other languages, using a class structure for organized method placement. If slow and fast meet, a cycle exists.
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).
1function ListNode(val) {
2 this.val = val;
3 this.next = null;
4}
5
6var hasCycle = function(head) {
7 const visited = new Set();
8 while (head) {
9 if (visited.has(head)) return true;
10 visited.add(head);
11 head = head.next;
12 }
13 return false;
14};JavaScript leverages a Set to remember nodes that have already been visited. Consequently, if a node reappears in the Set, a cycle is confirmed.