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 def __init__(self, x):
3 self.val = x
4 self.next = None
5
6class Solution:
7 def hasCycle(self, head: ListNode) -> bool:
8 slow, fast = head, head
9 while fast and fast.next:
10 slow = slow.next
11 fast = fast.next.next
12 if slow == fast:
13 return True
14 return FalseIn Python, we utilize a two-pointer approach with the slow and fast pointers. The detection of a cycle is determined by whether the pointers meet during traversal.
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).
1class ListNode:
2 def __init__(self, x):
3 self.val = x
4 self.next = None
5
6class Solution:
7 def hasCycle(self, head: ListNode) -> bool:
8 visited = set()
9 while head:
10 if head in visited:
11 return True
12 visited.add(head)
13 head = head.next
14 return FalseIn Python, a set is used to implement the logic similar to Java's HashSet. The cycle is detected by checking if a node has been seen before.