May 25, 2014

Find length of cycle in linked list in Java - Floyd cycle detection algorithm

Find length of cycle in a liked list is an application of Floyd cycle detection algorithm.In order to solve this problem, first we need to solve two problem in sequence - 1. find cycle in linked list in Java and 2. find beginning of cycle in linked list. Once we have found that beginning of  cycle, just traverse the cycle and manage a count until we reaches that starting node again. Refer above mentioned links for more details about cycle detection and finding beginning node of cycle. Below is the algorithm and sample code for finding length of cycle -
Algorithm:- 
1. First detecting cycle, then
2 .Find starting node of cycle
3. Find length of cycle (reach at beginning of beginning of cycle again)

Finding length of cycle:- 
static public int findLengthOfCycle(Node head) {
int length = 0;
if (head == null)
return 0;
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;
}


/* Find length of cycle - slowRef and fastRef referring same node */
slowReference = slowReference.next;
length++;
while (!slowReference.equals(fastReference)) {
slowReference = slowReference.next;
length++;
}
    }
return length;
}
Explanation:- While finding length of list, first we move slowReference and increment length. After that in while loop we traverse until again it meets fastReference.For each movement we increment length.

Below is the complete  sample program for finding length of cycle, if exist and return length of cycle.If cycle does not exist it return 0.
package com.devinline.linkedlist;

public class LengthOfCycleInCyclicSLL {

static Node head;

static public int findLengthOfCycle(Node head) {
int length = 0;
if (head == null)
return 0;
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;
}

/* Find length of cycle - slowRef and fastRef referring same node */
slowReference = slowReference.next;
length++;
while (!slowReference.equals(fastReference)) {
slowReference = slowReference.next;
length++;
}
}
return length;
}

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) {
LengthOfCycleInCyclicSLL cyc = new LengthOfCycleInCyclicSLL();
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);
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;
node6.next = node4; // cycle formed between node 6 and 4 - 62 is
// start
// of cycle

int lengthOfCycle = findLengthOfCycle(head);
System.out.println("Length of cycle is " + lengthOfCycle);

}

}
===Sample output====
Length of cycle is 3
=================

Location: Hyderabad, Telangana, India