top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

How to check whether a linked list is circular ?

0 votes
410 views
How to check whether a linked list is circular ?
posted Jul 23, 2014 by Chahat Sharma

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

+1 vote

Algorithm
Step 1: Take 2 pointers travelling at different speeds start from the head of the linked list called faster pointer and slower pointer.
Step 2: Iterate through a loop.
Step 3: If the faster pointer reaches a NULL pointer then return saying that the list is acyclic and not circular.
Step 4: If the faster pointer is ever equal to the slower pointer or the faster pointer's next pointer is ever equal to the slower pointer then return that the list is circular.
Step 5: Advance the slower pointer one node and faster pointer by 2 nodes.

Code

bool is_circular(Node *head)
{
   Node *slower, * faster;
   slower = head;
   faster = head->next; //start faster one node ahead

   while(true) {
     // if the faster pointer encounters a NULL element
     if( !faster || !faster->next)
       return false;
    //if faster pointer ever equals slower or faster's next
    //pointer is ever equal to slow then it's a circular list
     else if (faster == slower || faster->next == slower)
        return true;
     else{
       // advance the pointers
        slower = slower->next;
        faster = faster->next->next;
      }
   }
}
answer Jul 23, 2014 by Pardeep Kohli
Similar Questions
+1 vote

Can someone help me with algorithm and code?

+1 vote

What is the best logic or way to detected linked list has loop ?
And also what is the best way to find out that given linked list is circular ?

+1 vote

Can someone help me with the complete code C/C++.

...