大多数时候在 Java 面试中都会问这个问题来测试候选人的技能。 我们将学习两种有效的方法来解决在链表中检测循环或循环的问题。
- 使用散列法检测链表中的循环或循环。
- 通过使用弗洛伊德循环检测算法
问题简述
下面给出了示例图，以了解链表中的循环。
了解链表中循环或循环的图表
我们可以清楚地看到，链表的最后一个节点是引用了另一个节点，而不是引用了null。 这表明链表包含循环。
现在出现的问题是如何检测该链表包含循环。 让我们转向第一种方法来检测链表中的循环，即使用哈希。
通过Hashing检查联表中的循环
这种方法是最简单的方法之一。 简单地说，我们将遍历我们的列表并在集合中输入每个遇到的节点。 如果当前节点已经存在于集合中（它只是意味着该节点之前已经见过），这意味着链表中存在一个循环。
该解决方案是检测链表中循环的最简单有效的解决方案之一。 下面是使用散列法检测链表中循环的示例代码。
package com.linkedlistDSADemo;
import java.util.HashSet;
import java.util.Set;
public class DetectCycleUsingHashing {
static class Node {
int data;
Node next;
Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
public static void main(String[] args) {
int keys[] = {1, 2, 3, 4, 5}; // input keys
Node head = null; // initialiaze head with null
for (int i = keys.length - 1; i >= 0; i--) {
head = new Node(keys[i], head);
}
//now insert cycle
head.next.next.next.next.next = head.next;
if (findOrDetectCycle(head)) {
System.out.println("Cycle or Loop Present in the Linked List");
} else {
System.out.println("No cycle or loop present in the linked list");
}
}
private static boolean findOrDetectCycle(Node head) {
Node current = head;
Set<Node> set = new HashSet<>();
while (current != null) {
if (set.contains(current)) {
return true;
} else {
set.add(current);
}
current = current.next;
}
return false;
}
}输出：Cycle or Loop Present in the Linked List
这个解决方案的时间和空间复杂度是多少？
该解决方案的时间复杂度为 O(n)，其中 n 是链表中存在的节点数。 但是当涉及到空间复杂度时，需要额外的辅助空间 O(n)，因为我们在这种方法中使用了 Set。
我们如何在不使用额外空间的情况下解决在链表中检测循环或循环的问题？ 有什么解决办法吗？
答案是肯定的。 有一种算法 Floyd 的循环检测算法，通过使用该算法，我们可以在 O(n) 时间内解决这个问题，而无需使用额外的空间。
Floyd检查联表中的循环引用
Floyd 的循环检测算法是一种基于指针的算法，它使用两个指针，它们以不同的速度在序列中移动。 简单地说，我们在这种方法中有两个指针，考虑一个名为快速指针，另一个是慢速指针。 简单的想法是移动快指针的速度是慢指针的两倍。 并且这两个指针之间的距离每走一步就加一。
如果两个指针在某个点相遇，那么它只是意味着我们已经在链表中循环了。 如果两个指针在某个点没有相遇，那么这意味着我们在链表中没有任何循环或循环。
下面是使用 Floyd 循环检测算法检测链表中循环或循环的程序。
package com.linkedlistDSADemo;
public class DetectCycleLinkedList {
static class Node {
int data;
Node next;
Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
public static void main(String[] args) {
int keys[] = {1, 2, 3, 4, 5}; // input keys
Node head = null; // initialiaze head with null
for (int i = keys.length - 1; i >= 0; i--) {
head = new Node(keys[i], head);
}
//now insert cycle
head.next.next.next.next.next = head.next.next;
if (findOrDetectCycle(head)) {
System.out.println("Cycle or Loop Present in the Linked List");
} else {
System.out.println("No cycle or loop present in the linked list");
}
}
private static boolean findOrDetectCycle(Node head) {
Node slowPointer = head;
Node fastPointer = head;
Node curr = head;
while (fastPointer != null && fastPointer.next != null) {
fastPointer = fastPointer.next.next;//move by two
slowPointer = slowPointer.next;
/*
below condition only true if the list contains a cycle
*/
if (fastPointer == slowPointer) {
return true;
}
}
/*
if only reach here fastPointer and slowPointer does not meet
* */
return false;
}
}输出：Cycle or Loop Present in the Linked List
现在，如果我们试图找出这个解决方案的时间复杂度，那么它就是 O(n)。 由于我们通过使用弗洛伊德循环检测算法没有为这个实现使用任何额外的空间，所以这种方法不需要额外的辅助空间。
结论
这两种方法都可以有效地检测链表中的循环或循环。 但是使用 Floyd 循环检测算法的解决方案被认为是最佳解决方案，因为它在 O(n) 时间内解决了问题，而无需使用额外的空间。