public class CycleFreeLinkedList<T> {
private Node<T> first;
private Node<T> last;
public CycleFreeLinkedList() {
first = new Node<>();
}
public void appendToTail(T data) {
final Node l = last;
final Node<T> newNode = new Node(data);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
}
public void appendNodeToTail(Node<T> node) {
final Node l = last;
final Node<T> newNode = node;
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
}
public void detectCyclic() {
Node fast = first;
Node slow = first;
while (fast != null && fast.getNext() != null) {
fast = fast.getNext().getNext();
slow = slow.getNext();
//if fast and slow pointers are meeting then LinkedList is cyclic
if (fast == slow) {
throw new CyclicNodeException(fast.toString());
}
}
}
@Override
public String toString() {
detectCyclic();
StringBuilder output = new StringBuilder();
Node current = first.getNext();
while (current != null) {
output.append(current).append(" -> ");
current = current.getNext();
}
return output.toString();
}
public static class Node<T> {
Node next;
T data;
public Node() {
}
public Node(T data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
'}';
}
}
public static class CyclicNodeException extends RuntimeException {
public CyclicNodeException(String msg) {
super("There is a cyclic node in the list at - " + msg);
}
}
}Detect Cycle/Loop in Linked List
Upasana | July 25, 2020 | 2 min read | 46 views
DetectCycle in LinkedList using two pointers.
|
This solution is “Floyd’s Cycle-Finding Algorithm” as published in “Non-deterministic Algorithms” by Robert W. Floyd in 1967. It is also called “The Tortoise and the Hare Algorithm”. |
O(n) time complexity
Simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single pass through the cycle. Detecting a loop is then just detecting that the slow iterator has been lapped by the fast iterator.
Algorithm Steps
-
Use two pointers fast and slow
-
Move fast two nodes and slow one node in each iteration
-
If fast and slow meet then linked list contains cycle
-
if fast points to null or fast.next points to null then linked list is not cyclic
Java Source Code
Unit Test to detect Loops/Cycle
public class CycleFreeLinkedListTest {
@Rule
public ExpectedException thrown= ExpectedException.none();
@org.junit.Test
public void testIsNotCyclic() throws Exception {
CycleFreeLinkedList<String> linkedList = new CycleFreeLinkedList();
linkedList.appendToTail("101");
linkedList.appendToTail("201");
linkedList.appendToTail("301");
linkedList.appendToTail("401");
System.out.println("linkedList = " + linkedList);
}
@org.junit.Test
public void testIsCyclic() throws Exception {
CycleFreeLinkedList<String> linkedList = new CycleFreeLinkedList();
linkedList.appendToTail("101");
Node<String> cycle = new Node<>("201");
linkedList.appendNodeToTail(cycle);
linkedList.appendToTail("301");
linkedList.appendToTail("401");
linkedList.appendNodeToTail(cycle);
thrown.expect( CyclicNodeException.class );
thrown.expectMessage("There is a cyclic node in the list at - Node{data=401}");
System.out.println("linkedList = " + linkedList);
}
}Top articles in this category:
- What is difference between Vector and ArrayList, which one shall be preferred
- What is polymorphism in Java OOP
- Removing elements while iterating over a Java Collection
- Fail-Safe vs Fail-Fast Iterator in Java Collections Framework
- Difference between HashMap, LinkedHashMap and TreeMap
- What is purpose of Collections.unmodifiableCollection
- What are four principles of OOP, How aggregation is different than Composition?
Recommended books for interview preparation:
Book you may be interested in..
Book you may be interested in..
