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.
1class ListNode {
2 int val;
3 ListNode next;
4 ListNode(int x) {
5 val = x;
6 next = null;
7 }
8}
9
10public class Solution {
11 public boolean hasCycle(ListNode head) {
12 if (head == null) return false;
13 ListNode slow = head;
14 ListNode fast = head;
15 while (fast != null && fast.next != null) {
16 slow = slow.next;
17 fast = fast.next.next;
18 if (slow == fast) {
19 return true;
20 }
21 }
22 return false;
23 }
24}The Java solution uses two pointers, slow and fast. The move rate difference ensures that if there's a cycle, they'll meet; otherwise, the loop exits when fast or fast.next is null.
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).
1using System.Collections.Generic;
2
3public class ListNode {
4 public int val;
5 public ListNode next;
6 public ListNode(int x) {
7 val = x;
8 next = null;
9 }
10}
11
12public class Solution {
13 public bool HasCycle(ListNode head) {
14 HashSet<ListNode> visited = new HashSet<ListNode>();
15 while (head != null) {
16 if (visited.Contains(head)) return true;
17 visited.Add(head);
18 head = head.next;
19 }
20 return false;
21 }
22}The C# solution follows a logical pattern applying HashSet to track all encountered nodes. Cycle detection occurs when a node reappears in the set.