5 months, 1 week

# Coding Patterns: Fast & Slow Pointers

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.

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:
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 ComplexityO(N) where `N` is the number of nodes in the Linked Lists.

Space ComplexityO(1), algorithm runs in constant space.

HashMap Solution:

class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
hashMap = {}

i = 0

return True
break
i += 1
return False

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]:
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
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.

#### Responses(0)  Related