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 comment