假设您在Java中有一个链表结构。它由节点组成:
class Node {
Node next;
// some user data
}
每个节点都指向下一个节点，除了最后一个节点，它的next为空。假设有一种可能性，列表可以包含一个循环-即最后的节点，而不是有一个空值，有一个引用到列表中它之前的一个节点。
最好的写作方式是什么
boolean hasLoop(Node first)
如果给定的节点是带有循环的列表的第一个，则返回true，否则返回false ?你怎么能写出一个常数的空间和合理的时间呢?
下面是一个带有循环的列表的图片:
当前回答
你也可以使用上述答案中所建议的弗洛伊德乌龟算法。
该算法可以检查单链表是否具有闭合循环。 这可以通过迭代带有两个移动速度不同的指针的列表来实现。通过这种方式，如果存在一个循环，两个指针将在未来的某个时间点相遇。
请随意查看我关于链表数据结构的博客文章，在那里我还包含了一个用java语言实现上述算法的代码片段。
问候,
安德烈亚斯 （@xnorcode）
其他回答
你也可以使用上述答案中所建议的弗洛伊德乌龟算法。
该算法可以检查单链表是否具有闭合循环。 这可以通过迭代带有两个移动速度不同的指针的列表来实现。通过这种方式，如果存在一个循环，两个指针将在未来的某个时间点相遇。
请随意查看我关于链表数据结构的博客文章，在那里我还包含了一个用java语言实现上述算法的代码片段。
问候,
安德烈亚斯 （@xnorcode）
算法
public static boolean hasCycle (LinkedList<Node> list)
{
HashSet<Node> visited = new HashSet<Node>();
for (Node n : list)
{
visited.add(n);
if (visited.contains(n.next))
{
return true;
}
}
return false;
}
复杂性
Time ~ O(n)
Space ~ O(n)
下面是快速/慢速解决方案的改进，它正确地处理奇数长度的列表并提高了清晰度。
boolean hasLoop(Node first) {
Node slow = first;
Node fast = first;
while(fast != null && fast.next != null) {
slow = slow.next; // 1 hop
fast = fast.next.next; // 2 hops
if(slow == fast) // fast caught up to slow, so there is a loop
return true;
}
return false; // fast reached null, so the list terminates
}
如果链表结构实现了java.util.List. list。我们可以使用列表大小来跟踪我们在列表中的位置。
我们可以遍历节点，将当前节点的位置与上一个节点的位置进行比较。如果我们当前的位置超过了上一个位置，我们就检测到列表在某个地方有一个循环。
这种解决方案需要恒定的空间，但随着列表大小的增加，完成所需的时间会线性增加。
class LinkedList implements List {
Node first;
int listSize;
@Override
int size() {
return listSize;
}
[..]
boolean hasLoop() {
int lastPosition = size();
int currentPosition = 1;
Node next = first;
while(next != null) {
if (currentPosition > lastPosition) return true;
next = next.next;
currentPosition++;
}
return false;
}
}
或作为一种实用工具:
static boolean hasLoop(int size, Node first) {
int lastPosition = size;
int currentPosition = 1;
Node next = first;
while(next != null) {
if (currentPosition > lastPosition) return true;
next = next.next;
currentPosition++;
}
return false;
}
这种方法有空间开销，但实现更简单:
循环可以通过在Map中存储节点来标识。在放置节点之前;检查节点是否已经存在。如果节点已经存在于映射中，则意味着链表有循环。
public boolean loopDetector(Node<E> first) {
Node<E> t = first;
Map<Node<E>, Node<E>> map = new IdentityHashMap<Node<E>, Node<E>>();
while (t != null) {
if (map.containsKey(t)) {
System.out.println(" duplicate Node is --" + t
+ " having value :" + t.data);
return true;
} else {
map.put(t, t);
}
t = t.next;
}
return false;
}
