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;
}
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!!"); } }
Cycle found!!
NO Cycle found!!
==========================
0 comments:
Post a Comment