Mar 16, 2014

How to find beginning of the cycle in linked list in Java - Floyd cycle detection algorithm

In continuation to precious post, How to detect cycle in a linked list, the main agenda of this post is to discuss - "How to detect the node where cycle starts". Floyd's algorithm states, 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.
Floyd hypothesis for find Cycle Beginning node - Once tortoise and hare meets, put tortoise back to the beginning of the list and keep hare where they met. If we allow to both tortoise and hare move at the same speed (1 step for both), the first time they ever meet again will be the cycle beginning.Below is the sample code for finding starting node of cycle.

static public Node findStartOfCycle(Node head) {
 if (head == null)
  return null;
 Node fastReference = head;
 Node slowReference = head;
 /* Iterate linked list to detect cycle */
 while (fastReference != null && slowReference != null) {
  if (fastReference.next != null) {
   /* fast reference - crosses 2 nodes at a time */
   fastReference = fastReference.next.next;
  }
  if (slowReference != null) {
   /* fast reference - cross 1 node at a time */
   slowReference = slowReference.next;
  }
  if (fastReference!=null && slowReference!=null && fastReference.equals(slowReference)) {
   break;
  }
 }
 /*
  * Once cycle detected, place slowRef to start of linked list and traverse
  * linked list one node at a time- both slow & fast ref meet again at start of
  * node of cycle
  */
 if (fastReference != null && slowReference != null) {
  slowReference = head;
  while (fastReference != slowReference) {
   slowReference = slowReference.next;
   fastReference = fastReference.next;
  }
  return slowReference;
 }
 return null;
}

Refer this for more detail about - How does Floyd algorithm works and understand how after detecting cycle, slow reference and fast reference moves with same frequency and finds starting node of cycle.
Below is the complete program for how to detect and find the starting node of cycle.Consider the following sample linked list.
HEAD-->12-->18-->172-->62---->  632
                                        ^                |
                                         |               v
                                        121<--    192
public class FindStartNodeofCycle {
 static Node head;

static public Node findStartOfCycle(Node head) {
 if (head == null)
  return null;
 Node fastReference = head;
 Node slowReference = head;
 /* Iterate linked list to detect cycle */
 while (fastReference != null && slowReference != null) {
  if (fastReference.next != null) {
   /* fast reference - crosses 2 nodes at a time */
   fastReference = fastReference.next.next;
  }
  if (slowReference != null) {
   /* fast reference - cross 1 node at a time */
   slowReference = slowReference.next;
  }
  if (fastReference!=null && slowReference!=null && fastReference.equals(slowReference)) {
   break;
  }
 }
 /*
  * Once cycle detected, place slowRef to start of linked list and
  * traverse linked list one by one - they will meet again at start of
  * node of cycle
  */
 if (fastReference != null && slowReference != null) {
  slowReference = head;
  while (fastReference != slowReference) {
   slowReference = slowReference.next;
   fastReference = fastReference.next;
  }
  return slowReference;
 }
 return null;
}

 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) {
  FindStartNodeofCycle cyc = new FindStartNodeofCycle();
  Node node1 = cyc.new Node(12);
  head = node1;
  Node node2 = cyc.new Node(18);
  Node node3 = cyc.new Node(172);
  Node node4 = cyc.new Node(62);
  Node node5 = cyc.new Node(632);
  Node node6 = cyc.new Node(192);
  Node node7 = cyc.new Node(121);

head.next = node2;  head.next.next = node3;  head.next.next.next = node4;  head.next.next.next.next = node5;  head.next.next.next.next.next = node6;
  head.next.next.next.next.next.next = node7;
  node7.next = node4; // cycle formed between node 6 and 4 - 62 is start of cycle
  
  Node startOfCycle = findStartOfCycle(head);
  System.out.println("Data value at start of cycle is "
    + startOfCycle.data);

 }

}
======Sample output=========
Data value at start of cycle is 62
=========================
Location: Hyderabad, Telangana, India