How to detect cycle in linked list in java - Floyd cycle detection algorithm

Problem statement :- How to detect a given linked list is cyclic or having a cycle or not ?
Cycle in a linked list means, when we iterate given linked list we are never going to reach end of list, because end node of list is having reference of some intermediate node. Se the following diagram:-

In order to detect cycle in a linked list, we can use Floyd cycle detection algorithm(tortoise and hare's algorithm)- the hare moves two steps for every step of the tortoise. It states that, if we iterate given linked list with different speed (with two references of different frequency) and check whether both fast and slow reference point to same node or not, if linked list having any cycle it will detected else iteration will complete(end of list detected). Below is the sample code for cycle detection. It returns true, if cycle is detected or Question may be modified to return given node which creates cycle.

private boolean checkCycleinLinkedList(Node head) {
 if (head == null)
  return false;
 Node fastReference = head;
 Node slowReference = head;
 while (fastReference != null && slowReference != null) {
  if (fastReference.next != null) {
   /* hare- fast reference (crosses 2 nodes at a time) */
   fastReference = fastReference.next.next;
  }
  if (slowReference != null) {
   /* tortoise - slow reference (cross 1 node at a time) */
   slowReference = slowReference.next;
  }
  if (fastReference!= null && slowReference!=null && 
     fastReference.equals(slowReference)) {
  break;
 }
 }
 if (fastReference == null || slowReference == null) {
  return false;
 }
 return true;
}

Note:- In Floyd's algorithm, the hare moves two steps for every step of the tortoise. If the tortoise and hare ever meet, there is a cycle, and the meeting point is part of the cycle, but not necessarily the first node in the cycle.Another problem associated with cycle detection algorithm is find start node of cycle.

Time and space complexity :- Since each node of linked list is visited only once so time complexity is O(n) and space complexity is O(1).

Below is the complete sample program for cycle detection in linked list.

public class CheckCyclicLinkedList {
 static Node head;

 static private boolean checkCycleinLinkedList(Node head) {
  if (head == null)
   return false;
  Node fastReference = head;
  Node slowReference = head;
  while (fastReference != null && slowReference != null) {
   if (fastReference.next != null) {
    /* fast reference - crosses 2 nodes at a time */
   fastReference = fastReference.next.next;
   // System.out.println(fastReference.data);
  }
  if (slowReference != null) {
   /* fast reference - cross 1 node at a time */
   slowReference = slowReference.next;
   // System.out.println(slowReference.data);
  }
  if (fastReference!= null && slowReference!=null && fastReference.equals(slowReference)) {

   break;
  }
 }
 if (fastReference == null || slowReference == null) {
  return false;
 }
 return true;
}

class Node {
 public int data;
 public Node next; // reference(handler) for next Node.

 public Node(int data) {
  this.data = data;
  this.next = null;
 }
}

public static void main(String[] args) {
 CheckCyclicLinkedList cyc = new CheckCyclicLinkedList();
 Node node1 = cyc.new Node(12);
 head = node1;
 Node node2 = cyc.new Node(18);
 head.next = node2;
 Node node3 = cyc.new Node(172);
 head.next.next = node3;
 Node node4 = cyc.new Node(62);
 head.next.next.next = node4;
 head.next.next.next.next = node3;// cycle formed here
 boolean cycleStat = checkCycleinLinkedList(head);
 if (cycleStat)
  System.out.println("Cycle found!!");
 else
  System.out.println("NO Cycle found!!");

 /* second call cycle is removed */
 head.next.next.next.next = null;// cycle removed
 boolean cycleStat2 = checkCycleinLinkedList(head);
 if (cycleStat2)
  System.out.println("Cycle found!!");
 else
  System.out.println("NO Cycle found!!");
 }

}

=======Sample program=======
Cycle found!!
NO Cycle found!!
==========================