链接列表循环检测– Floyd的循环查找算法
在本教程中，我们将讨论一种非常流行的算法，该算法用于检测LinkedList是否具有循环。
称为弗洛伊德(Floyd)的循环查找算法。
LinkedList循环检测
当遍历整个LinkedList时没有NULL时，LinkedList中存在一个循环。
因此，为了检测LinkedList是否存在循环，我们可以遍历LinkedList，并将每个Node(如果已访问第一项)添加到已访问笔记的HashSet中。
到达HashSet中已经存在的节点后，我们就可以知道存在一个循环。
但是这种方法虽然更简单，但会占用另外的空间。
另一种方法是在LinkedList节点数据本身中为访问的节点设置标志。
但是同样，这种方法会占用一些另外的空间。
比我们之前使用的更多。
因此，检测回路的理想方法是使用Floyd的循环查找算法
Floyd的循环查找算法
弗洛伊德(Floyd)的循环查找算法使用两个指针以不同的速度移动。
如果存在一个周期，则两个指针将来都将指向相同的值。
弗洛伊德(Floyd)的循环查找算法类似于乌龟头发的故事。
让我们编写Java程序来创建我们自己的LinkedList类。
MyLinkedList.java
package com.theitroad.linkedlist.reverse;
/**
* A very simple linked list implementation
* Not to use in application, created to show the linked list
* operations, hence very minimal features
*
* @author hyman
*
*/
public class MyLinkedList {
public Node head;
public static class Node {
public Node next;
public Object data;
public Node(Object data) {
this.data = data;
next = null;
}
}
}
下列类包含检测LinkedList中的循环的方法。
package com.theitroad.linkedlist.loopDetection;
import com.theitroad.linkedlist.reverse.MyLinkedList;
import com.theitroad.linkedlist.reverse.MyLinkedList.Node;
public class DetectLinkedListLoop {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.head = new Node(1);
myLinkedList.head.next = new Node(2);
Node node = myLinkedList.head.next.next = new Node(3);
myLinkedList.head.next.next.next = new Node(4);
myLinkedList.head.next.next.next.next = new Node(5);
myLinkedList.head.next.next.next.next.next = node;
System.out.println("Has Loop? " + hasLoop(myLinkedList));
}
private static boolean hasLoop(MyLinkedList myLinkedList) {
Node head = myLinkedList.head;
Node slow = head;
Node fast = head;
boolean loop = false;
while (slow != null && fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
loop = true;
break;
}
}
return loop;
}
}
我们以快慢指针两倍的速度移动了快指针。
如果存在循环，则快指针和慢指针有时会相遇。
其中我们可以结束while语句并返回布尔值标志。
上面的代码返回一个" true"。
检测循环的第一个元素
为了检测循环的起始节点，我们需要在上述算法中增加另一步。
一旦快和慢指针相等。
将其中之一设置回LinkedList头的开头。
以相等的速度移动两个指针。
在它们再次相遇的节点处，将是循环的起始节点。
private static Node startNode(MyLinkedList myLinkedList) {
Node head = myLinkedList.head;
Node slow = head;
Node fast = head;
boolean loop = false;
while (slow != null && fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
loop = true;
break;
}
}
if (loop) {
slow = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
} else {
return new Node(Integer.MIN_VALUE);
}
}
在main中调用上述方法：
System.out.println("Start Node data: " + startNode(myLinkedList).data);
这将返回带有数据的节点3。
循环长度
找到循环的起点后，我们可以其中保留一个指针，并通过节点将另一个指针遍历，同时将长度增加1。
private static int lengthOfLoop(MyLinkedList myLinkedList) {
Node head = myLinkedList.head;
Node slow = head;
Node fast = head;
boolean loop = false;
while (slow != null && fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
loop = true;
break;
}
}
if (loop) {
int length = 0;
slow = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
do {
fast = fast.next;
length++;
} while (fast != slow);
return length;
}
return 0;
}
在main中调用上述方法：
System.out.println("Length of loop: " + lengthOfLoop(myLinkedList));
上例中的循环长度为3。
卸下环
为了删除循环，我们需要在上面的示例中添加另一个步骤：
一旦慢速指针和快速指针位于循环的起始节点，就将快速指针移动一个，直到其下一个指针等于慢速指针为止。
该快速指针的当前位置将是循环的最后一个节点。
我们需要将该节点的" next"设置为null。
private static Node removeLoop(MyLinkedList myLinkedList) {
Node head = myLinkedList.head;
Node slow = head;
Node fast = head;
boolean loop = false;
while (slow != null && fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
loop = true;
break;
}
}
if (loop) {
slow = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
while (fast.next != slow) {
fast = fast.next;
}
fast.next = null;
return head;
}
return head;
}
在main中调用上述方法：
myLinkedList.head = removeLoop(myLinkedList);
System.out.println("Has Loop? " + hasLoop(myLinkedList));
时间复杂度：O(n)辅助空间：O(1)
