Detect a cycle\loop in a singly linked list

Posted on Updated on

A singly linked list is made of nodes where each node has a pointer to the next node . And client can have only the pointer of head node. Now we need to check that does a linked list has a cycle or not.
By using following algorithm we can easily detect cycle with time complexity O(n).

boolean hasCycle(Node head){
      Node p1 = head;
      Node p2 = head;

      while(p1 != null || p2 != null){
         p1 = p1.next(); // Move forward by one place
         p2 = p2.next().next(); // Move forward by two places

         if(p1 == p2){
             return true; // It has a cycle.
         }
      }
     //If linked list does not has a cycle, than it will exit while loop after reaching end of the list.
      return false;
}

This is the easiest solution to dettect a cycle. We can also use “Floyd’s Cycle-Finding Algorithm” to find a cycle in linked list.
Example: Detect an loop in below linked list. It has cycle – C->D->E>C
linkedlist_cycle

Now we are using above algorithm to detect a loop in this linked list.
Initially both pointers will point to head.
iteration1
Iteration 1
iteration2
Iteration 2
iteration3
Iteration 3
iteration4

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s