假设您在Java中有一个链表结构。它由节点组成:
class Node {
Node next;
// some user data
}
每个节点都指向下一个节点，除了最后一个节点，它的next为空。假设有一种可能性，列表可以包含一个循环-即最后的节点，而不是有一个空值，有一个引用到列表中它之前的一个节点。
最好的写作方式是什么
boolean hasLoop(Node first)
如果给定的节点是带有循环的列表的第一个，则返回true，否则返回false ?你怎么能写出一个常数的空间和合理的时间呢?
下面是一个带有循环的列表的图片:
当前回答
您甚至可以在常数O(1)时间内完成(尽管它不是非常快或有效):计算机内存可以容纳的节点数量是有限的，比如N条记录。如果遍历超过N条记录，那么就有一个循环。
其他回答
我看不出有任何方法可以让这花费固定的时间或空间，两者都会随着列表的大小而增加。
我将使用IdentityHashMap(假设还没有IdentityHashSet)并将每个节点存储到映射中。在存储节点之前，您可以对其调用containsKey。如果节点已经存在，则有一个周期。
ItentityHashMap使用==而不是.equals，这样你就可以检查对象在内存中的位置，而不是它是否具有相同的内容。
如果允许我们嵌入类Node，我将像下面实现的那样解决这个问题。hasLoop()在O(n)时间内运行，并且只占用计数器的空间。这是不是一个合适的解决方案?或者是否有一种不嵌入Node的方法?(显然，在真正的实现中会有更多的方法，如RemoveNode(Node n)等。)
public class LinkedNodeList {
Node first;
Int count;
LinkedNodeList(){
first = null;
count = 0;
}
LinkedNodeList(Node n){
if (n.next != null){
throw new error("must start with single node!");
} else {
first = n;
count = 1;
}
}
public void addNode(Node n){
Node lookingAt = first;
while(lookingAt.next != null){
lookingAt = lookingAt.next;
}
lookingAt.next = n;
count++;
}
public boolean hasLoop(){
int counter = 0;
Node lookingAt = first;
while(lookingAt.next != null){
counter++;
if (count < counter){
return false;
} else {
lookingAt = lookingAt.next;
}
}
return true;
}
private class Node{
Node next;
....
}
}
这是我在java中的解决方案
boolean detectLoop(Node head){
Node fastRunner = head;
Node slowRunner = head;
while(fastRunner != null && slowRunner !=null && fastRunner.next != null){
fastRunner = fastRunner.next.next;
slowRunner = slowRunner.next;
if(fastRunner == slowRunner){
return true;
}
}
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;
}
public boolean isCircular() {
if (head == null)
return false;
Node temp1 = head;
Node temp2 = head;
try {
while (temp2.next != null) {
temp2 = temp2.next.next.next;
temp1 = temp1.next;
if (temp1 == temp2 || temp1 == temp2.next)
return true;
}
} catch (NullPointerException ex) {
return false;
}
return false;
}
