The fast and slow pointer technique (also known as the tortoise and hare algorithm) uses two pointers to determine traits about directional data structures. This can be an array, singly-linked list, or a graph. It is often applied to determine if there are any cycles in the data structure and is therefore also known as Floyd’s Cycle Detection Algorithm.
To implement this algorithm, the algorithm is to start with two pointers, slow and fast from the head of linked list. We move slow one node at a time and fast two nodes at a time. If there is a loop, then they will definitely meet. Usually, the slow pointer will move ahead one step while the fast pointer moves ahead two. This approach works because of the following facts. When the slow pointer enters the loop, the fast pointer must be inside the loop.
Problem: Linked List Cycle
LeetCode 141 - Linked List Cycle [easy]
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
fast, slow = head, head
while fast and fast.next:
fast, slow = fast.next.next, slow.next
if fast == slow:
return True
return False
The fast pointer moves two steps and the slow pointer moves one step, and they both meet.
Time Complexity: O(N) where N is the number of nodes in the Linked Lists.
Space Complexity: O(1), algorithm runs in constant space.
HashMap Solution:
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
hashMap = {}
i = 0
while head:
if head in hashMap:
return True
break
hashMap[head] = i
i += 1
head = head.next
return False
Problem: Linked List Cycle II
LeetCode 142 - Linked List Cycle II [medium]
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.
Do not modify the linked list.
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow, fast = head, head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
break
if not fast or not fast.next:
return None
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return fast
Time Complexity: O(N) where N is the number of nodes in the Linked Lists.
Space Complexity: O(1), algorithm runs in constant space.
When the problem involves something related to cyclic data structures, you should think about Fast & Slow Pointers pattern.
