Cycle Detection in LinkedList

Say, we have a linked list
    6->8->9->10->4->3->10.....

If last but one node points to 10, then we will end up in an infinite loop.
So the question here is - how to detect this cycle.

This can be identified using the Floyd Cycle detection algorithm.

http://en.wikipedia.org/wiki/Cycle_detection 

This algorithm is also known as Tortoise and Hare algorithm, In this we will have two references, one reference jumps to one position and other one jumps to 2 positions, we do this continuously until we iterate all the elements from both the references or if both the reference points to same node, In each iteration we will compare the node value from reference one and two.

Below is the simple java code to find the cycle detection.

Here we have introduced two references
first and second,  
Iteration 1, first -> 6, second ->8
Iteration 2, first -> 8, second ->10
Iteration 3, first -> 9, second ->3
Iteration 4, first -> 10, second ->4
Iteration 5, first -> 4, second ->10
Iteration 6, first -> 3, second ->3

At iteration 6, both the node values will be equal and we stop the iteration.

 


 
     public static boolean isCyclic(LinkedList list) {
        LinkedList.Node first = list.head(); // get the head node
        LinkedList.Node second = list.head.getNext(); // get the second node
       
        while(true) {
            if(first !=null && second != null && first.getData() != null && second.getData() !=null) {
                if(first.getData().equals(second.getData())) {
                    return true;
                } else {
                    first = first.getNext();
                    if(second.getNext() != null)
                        second = second.getNext().getNext();
                    else
                        second =  null;
                }
            } else
                return false;
        }
    }