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;
}
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);
}
}
Length of cycle is 3
=================
0 comments:
Post a Comment