假设您在Java中有一个链表结构。它由节点组成:
class Node {
Node next;
// some user data
}
每个节点都指向下一个节点，除了最后一个节点，它的next为空。假设有一种可能性，列表可以包含一个循环-即最后的节点，而不是有一个空值，有一个引用到列表中它之前的一个节点。
最好的写作方式是什么
boolean hasLoop(Node first)
如果给定的节点是带有循环的列表的第一个，则返回true，否则返回false ?你怎么能写出一个常数的空间和合理的时间呢?
下面是一个带有循环的列表的图片:
当前回答
你可以使用弗洛伊德的周期寻找算法，也被称为乌龟和野兔算法。 其思想是对列表有两个引用，并以不同的速度移动它们。一个向前移动1个节点，另一个向前移动2个节点。
如果链表有一个循环 一定会见面的。 或者 这两个引用(或下一个) 将变为null。
实现算法的Java函数:
boolean hasLoop(Node first) {
if(first == null) // list does not exist..so no loop either
return false;
Node slow, fast; // create two references.
slow = fast = first; // make both refer to the start of the list
while(true) {
slow = slow.next; // 1 hop
if(fast.next != null)
fast = fast.next.next; // 2 hops
else
return false; // next node null => no loop
if(slow == null || fast == null) // if either hits null..no loop
return false;
if(slow == fast) // if the two ever meet...we must have a loop
return true;
}
}
其他回答
如果链表结构实现了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;
}
下面是快速/慢速解决方案的改进，它正确地处理奇数长度的列表并提高了清晰度。
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，但我仍然认为它属于这里:
当我们在现代体系结构中使用指针时，我们可以期望它们是CPU字对齐的。对于64位体系结构，这意味着指针的前3位始终为零。这让我们可以使用这个内存来标记我们已经见过的指针，通过对它们的第一个比特写入1。
如果我们遇到一个指针，它的第一个位已经写了1，那么我们已经成功地找到了一个循环，之后我们需要再次遍历结构，并将这些位屏蔽掉。完成了!
这种方法被称为指针标记，它在低级编程中被过度使用，例如Haskell在一些优化中使用它。
您甚至可以在常数O(1)时间内完成(尽管它不是非常快或有效):计算机内存可以容纳的节点数量是有限的，比如N条记录。如果遍历超过N条记录，那么就有一个循环。
你可以使用弗洛伊德的周期寻找算法，也被称为乌龟和野兔算法。 其思想是对列表有两个引用，并以不同的速度移动它们。一个向前移动1个节点，另一个向前移动2个节点。
如果链表有一个循环 一定会见面的。 或者 这两个引用(或下一个) 将变为null。
实现算法的Java函数:
boolean hasLoop(Node first) {
if(first == null) // list does not exist..so no loop either
return false;
Node slow, fast; // create two references.
slow = fast = first; // make both refer to the start of the list
while(true) {
slow = slow.next; // 1 hop
if(fast.next != null)
fast = fast.next.next; // 2 hops
else
return false; // next node null => no loop
if(slow == null || fast == null) // if either hits null..no loop
return false;
if(slow == fast) // if the two ever meet...we must have a loop
return true;
}
}
