Detect a cycle\loop in a singly linked list
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
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
This entry was posted in Data Structures, Uncategorized and tagged algorithm, cycle in list, data structure, linked list, linked list with java, list data structure, loop in list, problem.