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 =; // Move forward by one place
         p2 =; // 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

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

Leave a Reply

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

You are commenting using your 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