假设您在Java中有一个链表结构。它由节点组成:
class Node {
Node next;
// some user data
}
每个节点都指向下一个节点，除了最后一个节点，它的next为空。假设有一种可能性，列表可以包含一个循环-即最后的节点，而不是有一个空值，有一个引用到列表中它之前的一个节点。
最好的写作方式是什么
boolean hasLoop(Node first)
如果给定的节点是带有循环的列表的第一个，则返回true，否则返回false ?你怎么能写出一个常数的空间和合理的时间呢?
下面是一个带有循环的列表的图片:
当前回答
这是我在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 hasLoop(Node start){
TreeSet<Node> set = new TreeSet<Node>();
Node lookingAt = start;
while (lookingAt.peek() != null){
lookingAt = lookingAt.next;
if (set.contains(lookingAt){
return false;
} else {
set.put(lookingAt);
}
return true;
}
// Inside our Node class:
public Node peek(){
return this.next;
}
请原谅我的无知(我对Java和编程仍然相当陌生)，但为什么上面的方法不能工作呢?
I guess this doesn't solve the constant space issue... but it does at least get there in a reasonable time, correct? It will only take the space of the linked list plus the space of a set with n elements (where n is the number of elements in the linked list, or the number of elements until it reaches a loop). And for time, worst-case analysis, I think, would suggest O(nlog(n)). SortedSet look-ups for contains() are log(n) (check the javadoc, but I'm pretty sure TreeSet's underlying structure is TreeMap, whose in turn is a red-black tree), and in the worst case (no loops, or loop at very end), it will have to do n look-ups.
这是我在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;
}
检测链表中的循环可以用最简单的方法之一来完成，使用hashmap会导致O(N)复杂度，使用基于排序的方法会导致O(NlogN)复杂度。
当您从head开始遍历列表时，创建一个已排序的地址列表。当您插入一个新地址时，检查该地址是否已经在已排序的列表中，这需要O(logN)复杂度。
// To detect whether a circular loop exists in a linked list
public boolean findCircularLoop() {
Node slower, faster;
slower = head;
faster = head.next; // start faster one node ahead
while (true) {
// if the faster pointer encounters a NULL element
if (faster == null || faster.next == null)
return false;
// if faster pointer ever equals slower or faster's next
// pointer is ever equal to slower then it's a circular list
else if (slower == faster || slower == faster.next)
return true;
else {
// advance the pointers
slower = slower.next;
faster = faster.next.next;
}
}
}
