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.
1function ListNode(val) {
2 this.val = val;
3 this.next = null;
4}
5
6var hasCycle = function(head) {
7 let slow = head, fast = head;
8 while (fast && fast.next) {
9 slow = slow.next;
10 fast = fast.next.next;
11 if (slow === fast) return true;
12 }
13 return false;
14};The JavaScript function leverages the same logic of two pointers. Different speeds of traversal will determine if a cycle exists when the pointers align.
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).
1import java.util.HashSet;
2import java.util.Set;
3
4class ListNode {
5 int val;
6 ListNode next;
7 ListNode(int x) {
8 val = x;
9 next = null;
10 }
11}
12
13public class Solution {
14 public boolean hasCycle(ListNode head) {
15 Set<ListNode> visited = new HashSet<>();
16 while (head != null) {
17 if (visited.contains(head)) {
18 return true;
19 }
20 visited.add(head);
21 head = head.next;
22 }
23 return false;
24 }
25}In Java, a HashSet is used to store nodes. This approach efficiently tracks seen nodes to detect cycles.