查找链表是否包含循环的算法
迭代链表时使用快速和慢速两个指针。快速指针在每次迭代中移动两个节点，而慢速指针移动到一个节点。如果链表包含循环或循环，那么在迭代过程中，快指针和慢指针都会在某个点上相遇。如果它们不相交，并且快速或慢速将指向空，那么链表就不是循环的，它不包含任何循环。这是精确的算法
1）使用快速和慢速两个指针
2）每次迭代快速移动两个节点，慢速移动一个节点
3）如果快速和慢速相遇，则链表包含循环
4）如果fast指向空或fast.next指向空，则链表不是循环的。
下一部分包含Java程序来检查链表是否包含循环，这是上述算法的精确实现。该算法也被称为Floyd的循环查找算法，通常被称为Tortoise and Hare算法，用于查找链表中的循环。
Java程序检查链表是否为循环
这个Java程序使用LinkedList（不Java.UTI.LIKEDLIST）和链表的前一个节点类，修改了添加ToStTrn（）方法和AppEntoTead（）方法。另外，链表的iscyclic（）方法用于实现逻辑，以确定链表是否包含循环。随后is cyclic（）如果链表是循环的，则返回true，否则返回false。
/*
* Java class to represent linked list data structure.
*/
public class LinkedList {
private Node head;
public LinkedList() { this.head = new Node("head"); }
public Node head() { return head;}
public void appendIntoTail(Node node) {
Node current = head;
//find last element of LinkedList i.e. tail
while(current.next() != null){
current = current.next();
}
//appending new node to tail in LinkedList
current.setNext(node);
}
/*
* If singly LinkedList contains Cycle then following would be true
* 1) slow and fast will point to same node i.e. they meet
* On the other hand if fast will point to null or next node of
* fast will point to null then LinkedList does not contains cycle.
*/
public boolean isCyclic(){
Node fast = head;
Node slow = head;
while(fast!= null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
//if fast and slow pointers are meeting then LinkedList is cyclic
if(fast == slow ){
return true;
}
}
return false;
}
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
Node current = head.next();
while(current != null){
sb.append(current).append("-->");
current = current.next();
}
sb.delete(sb.length() - 3, sb.length()); // to remove --> from last node
return sb.toString();
}
public static class Node {
private Node next;
private String data;
public Node(String data) {
this.data = data;
}
public String data() { return data; }
public void setData(String data) { this.data = data;}
public Node next() { return next; }
public void setNext(Node next) { this.next = next; }
@Override
public String toString() {
return this.data;
}
}
}
|
测试循环的链表
在本节中，我们将使用带有两个链表的Java main方法测试，一个包含循环而另一个不循环。 您甚至可以为isCyclic（）方法编写JUnit测试用例，以测试不同位置的循环的不同链表。 这是链表不包含任何循环的第一个测试。
/**
*
* Java program to find if LinkedList contains loop or cycle or not.
* This example uses two pointer approach to detect cycle in linked list.
* Fast pointer moves two node at a time while slow pointer moves one node.
* If linked list contains any cycle or loop then both pointer will meet some time.
*
* @author Javin Paul
*/
public class LinkedListTest {
public static void main(String args[]) {
//creating LinkedList with 5 elements including head
LinkedList linkedList = new LinkedList();
linkedList.appendIntoTail(new LinkedList.Node("101"));
linkedList.appendIntoTail(new LinkedList.Node("201"));
linkedList.appendIntoTail(new LinkedList.Node("301"));
linkedList.appendIntoTail(new LinkedList.Node("401"));
System.out.println("Linked List : " + linkedList);
if(linkedList.isCyclic()){
System.out.println("Linked List is cyclic as it contains cycles or loop");
}else{
System.out.println("LinkedList is not cyclic, no loop or cycle found");
}
}
}
Output:
Linked List : 101-->201-->301-->401
LinkedList is not cyclic, no loop or cycle found
|
现在让我们改变链表，使其包含循环
//creating LinkedList with 5 elements including head
LinkedList linkedList = new LinkedList();
linkedList.appendIntoTail(new LinkedList.Node("101"));
LinkedList.Node cycle = new LinkedList.Node("201");
linkedList.appendIntoTail(cycle);
linkedList.appendIntoTail(new LinkedList.Node("301"));
linkedList.appendIntoTail(new LinkedList.Node("401"));
linkedList.appendIntoTail(cycle);
//don't call toString method in case of cyclic linked list, it will throw OutOfMemoryError
//System.out.println("Linked List : " + linkedList);
if(linkedList.isCyclic()){
System.out.println("Linked List is cyclic as it contains cycles or loop");
}else{
System.out.println("LinkedList is not cyclic, no loop or cycle found");
}
Output:
Linked List is cyclic as it contains cycles or loop
|