Brent's Algorithm

Brent's Cycle detection Algorithm

Given a linked list, check if the linked list has loop or not. Below diagram shows a linked list with a loop.


 

Brent’s cycle detection algorithm is analogous to Floyd's algorithm because it also uses two pointer technique. But there's some difference in their approaches. Here we make one pointer stationary till every iteration and teleport it to other pointer at every power of two. the beginning of the cycle is decided by the littlest power of two at which they meet. This improves upon the constant factor of Floyd’s algorithm by reducing the amount of calls.

  1. Move fast pointer (or second_pointer) in powers of two until we discover a loop. After every power, we reset slow pointer (or first_pointer) to previous value of second pointer. Reset length to 0 after every every power.
  2. The condition for loop testing is first_pointer and second_pointer become same. And loop isn't present if second_pointer becomes NULL.
  3. The condition for loop testing is first_pointer and second_pointer become same. And loop isn't present if second_pointer becomes NULL3. once we begin of loop, we've length of loop.
  4. We reset first_pointer to go and second_pointer to node at position head + length.
  5. Now we move both pointers one by one to seek out beginning of loop.

Comparison with Floyd’s Algorithm:

(1) Finds the length of loop in first cycle detection loop itself. No extra work is required for this.

(2) We only move second in every iteration and avoid moving first (which are often costly if moving to next node involves evaluating a function).

Program: C++

 

// CPP program to implement Brent's cycle  
// detection algorithm to detect cycle in
// a linked list.
#include <stdio.h>
#include <stdlib.h>
 
/* Link list node */
struct Node {
    int data;
    struct Node* next;
};
 
/* This function detects loop in the list
If loop was there in the list then it returns,
the first node of loop otherwise returns NULL */
struct Node* detectCycle(struct Node* head)
{
    // if head is null then no loop
    if (head == NULL)  
        return NULL;     
 
    struct Node* first_pointer = head;
    struct Node* second_pointer = head->next;
    int power = 1;
    int length = 1;
 
    // This loop runs till we find the loop.
    // If there is no loop then second_pointer
    // ends at NULL .
    while (second_pointer != NULL &&  
           second_pointer != first_pointer) {
 
        // condition after which we will
        // update the power and length as
        // smallest power of two gives the
        // start of cycle.
        if (length == power) {
 
            // updating the power.
            power *= 2;
 
            // updating the length
            length = 0;
 
            first_pointer = second_pointer;
        }
 
        second_pointer = second_pointer->next;
        ++length;
    }
 
    // if it is null then no loop
    if (second_pointer == NULL)  
        return NULL;     
 
    // Otherwise length stores actual length  
    // of loop.
    // If needed, we can also print length of
    // loop.
    // printf("Length of loop is %d\n", length);
 
    // Now set first_pointer to the beginning
    // and second_pointer to beginning plus
    // cycle length which is length.
    first_pointer = second_pointer = head;
    while (length > 0) {
        second_pointer = second_pointer->next;
        --length;
    }
 
    // Now move both pointers at same speed so
    // that they meet at the beginning of loop.
    while (second_pointer != first_pointer) {
        second_pointer = second_pointer->next;
        first_pointer = first_pointer->next;
    }
 
    // If needed, we can also print length of
    // loop.
    // printf("Length of loop is %d", length);
 
    return first_pointer;
}
 
struct Node* newNode(int key)
{
    struct Node* temp =  
      (struct Node*)malloc(sizeof(struct Node));
    temp->data = key;
    temp->next = NULL;
    return temp;
}
 
// Driver program to test above function
int main()
{
    struct Node* head = newNode(50);
    head->next = newNode(20);
    head->next->next = newNode(15);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(10);
 
    // Create a loop for testing  
    head->next->next->next->next->next =  
                              head->next->next;
 
    Node *res = detectCycle(head);
    if (res == NULL)
        printf("No loop");
    else
        printf("Loop is present at %d", res->data);
    return 0;
}
  
Program: Python

 # Python program to implement
# Brent's cycle detection
# algorithm to detect cycle
# in a linked list.
 
# Node class
class Node:
   
    # Constructor to initialize
    # the node object
    def __init__(self, data):
        self.data = data
        self.next = None
   
class LinkedList:
   
    # Function to initialize head
    def __init__(self):
        self.head = None
   
    # Function to insert a new Node
    #  at the beginning
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node
   
    # Utility function to prit
    # the linked LinkedList
    def printList(self):
        temp = self.head
        while(temp):
            print (temp.data,end=" ")
            temp = temp.next
   
   
    def detectCycle(self):
         # if head is null
         # then no loop
         temp=self.head
           
         if not (temp):
             return False
         first_p=temp
         second_p=temp.next
         power = 1
         length = 1
           
         # This loop runs till we
         # find the loop. If there
         # is no loop then second
         # pointer ends at NULL  
         while (second_p and second_p!= first_p):
          
             # condition after which  
             # we will update the power
             # and length as smallest
             # power of two gives
             # the start of cycle.
           if (length == power):
   
            # updating the power.
                power *= 2
   
            # updating the length
                length = 0
   
                first_p = second_p
               
           second_p = second_p.next
           length=length+1
         # if it is null then no loop
         if not (second_p) :
             return    
   
    # Otherwise length stores
    # actual length of loop.
    # If needed, we can also
    # print length of loop.
    # print("Length of loop is ")
    # print (length)
   
    # Now set first_pointer
    # to the beginning and
    # second_pointer to
    # beginning plus cycle
    # length which is length.
         first_p = second_p = self.head
         while (length > 0):
             second_p = second_p.next
             length=length-1
          
            # Now move both pointers
            # at same speed so that
            # they meet at the
            # beginning of loop.
         while (second_p!= first_p) :
               second_p = second_p.next
               first_p = first_p.next
      
         return first_p
   
# Driver program for testing
llist = LinkedList()
llist.push(50)
llist.push(20)
llist.push(15)
llist.push(4)
llist.push(10)
   
# Create a loop for testing
llist.head.next.next.next.next.next = llist.head.next.next;
res=llist.detectCycle()
if( res.data):
    print ("loop found at ",end=' ')
    print (res.data)
else :
    print ("No Loop ")


Output:

Loop is present at 15

Time Complexity: O(m + n) where m is that the smallest index of the sequence which is that the beginning of a cycle, and n is that the cycle’s length.

Auxiliary Space: – O(1) auxiliary

Comments

Post a Comment