1 month, 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. 

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.

Fast & Slow Pointers Solution                                                                                    

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 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                                                                               

        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.

Solution:                                                                                                                                                                     

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.

 


Responses(0)







Related