Java 如何检测链表中的循环？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2663115/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to detect a loop in a linked list?
提问by jjujuma
Say you have a linked list structure in Java. It's made up of Nodes:
假设您在 Java 中有一个链表结构。它由节点组成：
class Node {
Node next;
// some user data
}
and each Node points to the next node, except for the last Node, which has null for next. Say there is a possibility that the list can contain a loop - i.e. the final Node, instead of having a null, has a reference to one of the nodes in the list which came before it.
并且每个节点都指向下一个节点，除了最后一个节点，下一个节点为空。假设列表有可能包含一个循环——即最后一个节点，而不是一个空节点，引用列表中在它之前的节点之一。
What's the best way of writing
什么是最好的写作方式
boolean hasLoop(Node first)
which would return trueif the given Node is the first of a list with a loop, and falseotherwise? How could you write so that it takes a constant amount of space and a reasonable amount of time?
true如果给定的 Node 是带有循环的列表的第一个，它会返回，false否则返回？你怎么写才能占用恒定的空间和合理的时间？
Here's a picture of what a list with a loop looks like:
这是带有循环的列表的样子的图片：
采纳答案by codaddict
You can make use of Floyd's cycle-finding algorithm, also known as tortoise and hare algorithm.
The idea is to have two references to the list and move them at different speeds. Move one forward by 1node and the other by 2nodes.
您可以使用Floyd 的寻环算法，也称为龟兔算法。
这个想法是对列表有两个引用并以不同的速度移动它们。一个由1节点向前移动，另一个由节点向前移动2。
- If the linked list has a loop they will definitelymeet.
- Else either of
the two references(or their
next) will becomenull.
- 如果链表有一个循环，它们肯定会相遇。
- 否则两个引用（或它们的
next）中的任何一个都将变为null.
Java function implementing the algorithm:
实现算法的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;
}
}
回答by Larry
Take a look at Pollard's rho algorithm. It's not quite the same problem, but maybe you'll understand the logic from it, and apply it for linked lists.
看看Pollard 的 rho 算法。这不是完全相同的问题，但也许您会从中理解逻辑，并将其应用于链表。
(if you're lazy, you can just check out cycle detection-- check the part about the tortoise and hare.)
（如果你很懒，你可以查看周期检测——查看关于乌龟和兔子的部分。）
This only requires linear time, and 2 extra pointers.
这只需要线性时间和 2 个额外的指针。
In Java:
在 Java 中：
boolean hasLoop( Node first ) {
if ( first == null ) return false;
Node turtle = first;
Node hare = first;
while ( hare.next != null && hare.next.next != null ) {
turtle = turtle.next;
hare = hare.next.next;
if ( turtle == hare ) return true;
}
return false;
}
(Most of the solution do not check for both nextand next.nextfor nulls. Also, since the turtle is always behind, you don't have to check it for null -- the hare did that already.)
（大多数解决方案不会同时检查nullnext和next.nextnull。此外，由于乌龟总是在后面，因此您不必检查它是否为 null——野兔已经这样做了。）
回答by Sparky
The following may not be the best method--it is O(n^2). However, it should serve to get the job done (eventually).
以下可能不是最好的方法——它是 O(n^2)。但是，它应该有助于完成工作（最终）。
count_of_elements_so_far = 0;
for (each element in linked list)
{
search for current element in first <count_of_elements_so_far>
if found, then you have a loop
else,count_of_elements_so_far++;
}
回答by TofuBeer
I cannot see any way of making this take a fixed amount of time or space, both will increase with the size of the list.
我看不出有任何方法可以使这花费固定的时间或空间，两者都会随着列表的大小而增加。
I would make use of an IdentityHashMap (given that there is not yet an IdentityHashSet) and store each Node into the map. Before a node is stored you would call containsKey on it. If the Node already exists you have a cycle.
我会使用 IdentityHashMap（假设还没有 IdentityHashSet）并将每个节点存储到地图中。在存储节点之前，您将对其调用 containsKey。如果节点已经存在，你就有了一个循环。
ItentityHashMap uses == instead of .equals so that you are checking where the object is in memory rather than if it has the same contents.
ItentityHashMap 使用 == 而不是 .equals 以便您检查对象在内存中的位置，而不是它是否具有相同的内容。
回答by meriton
An alternative solution to the Turtle and Rabbit, not quite as nice, as I temporarily change the list:
海龟和兔子的替代解决方案，不太好，因为我暂时更改了列表：
The idea is to walk the list, and reverse it as you go. Then, when you first reach a node that has already been visited, its next pointer will point "backwards", causing the iteration to proceed towards firstagain, where it terminates.
这个想法是遍历列表，并在进行时反转它。然后，当您第一次到达已经访问过的节点时，它的下一个指针将指向“向后”，导致迭代first再次进行，并在那里终止。
Node prev = null;
Node cur = first;
while (cur != null) {
Node next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
boolean hasCycle = prev == first && first != null && first.next != null;
// reconstruct the list
cur = prev;
prev = null;
while (cur != null) {
Node next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return hasCycle;
Test code:
测试代码：
static void assertSameOrder(Node[] nodes) {
for (int i = 0; i < nodes.length - 1; i++) {
assert nodes[i].next == nodes[i + 1];
}
}
public static void main(String[] args) {
Node[] nodes = new Node[100];
for (int i = 0; i < nodes.length; i++) {
nodes[i] = new Node();
}
for (int i = 0; i < nodes.length - 1; i++) {
nodes[i].next = nodes[i + 1];
}
Node first = nodes[0];
Node max = nodes[nodes.length - 1];
max.next = null;
assert !hasCycle(first);
assertSameOrder(nodes);
max.next = first;
assert hasCycle(first);
assertSameOrder(nodes);
max.next = max;
assert hasCycle(first);
assertSameOrder(nodes);
max.next = nodes[50];
assert hasCycle(first);
assertSameOrder(nodes);
}
回答by smessing
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;
}
Forgive me my ignorance (I'm still fairly new to Java and programming), but why wouldn't the above work?
原谅我的无知（我对 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.
我想这并不能解决恒定空间问题......但它至少在合理的时间内到达那里，对吗？它只会占用链表的空间加上具有 n 个元素的集合的空间（其中 n 是链表中的元素数，或到达循环之前的元素数）。对于时间，我认为最坏情况分析会建议 O(nlog(n))。contains() 的 SortedSet 查找是 log(n)（检查 javadoc，但我很确定 TreeSet 的底层结构是 TreeMap，它又是一棵红黑树），在最坏的情况下（没有循环，或在最后循环），它将必须进行 n 次查找。
回答by smessing
If we're allowed to embed the class Node, I would solve the problem as I've implemented it below. hasLoop()runs in O(n) time, and takes only the space of counter. Does this seem like an appropriate solution? Or is there a way to do it without embedding Node? (Obviously, in a real implementation there would be more methods, like RemoveNode(Node n), etc.)
如果我们被允许嵌入 class Node，我会解决这个问题，因为我已经在下面实现了它。hasLoop()在 O(n) 时间内运行，并且只占用 的空间counter。这看起来是一个合适的解决方案吗？或者有没有办法在不嵌入的情况下做到这一点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;
....
}
}
回答by Carl M?sak
The user unicornaddicthas a nice algorithm above, but unfortunately it contains a bug for non-loopy lists of odd length >= 3. The problem is that fastcan get "stuck" just before the end of the list, slowcatches up to it, and a loop is (wrongly) detected.
用户unicornacci上面有一个很好的算法，但不幸的是它包含一个错误，用于奇数长度 >= 3 的非循环列表。问题是fast可能会在列表末尾之前“卡住”，slow赶上它，并且循环被（错误地）检测到。
Here's the corrected algorithm.
这是更正后的算法。
static 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 = null;
else
fast = fast.next.next; // 2 hops.
if(fast == null) // if fast hits null..no loop.
return false;
if(slow == fast) // if the two ever meet...we must have a loop.
return true;
}
}
回答by Dave L.
Here's a refinement of the Fast/Slow solution, which correctly handles odd length lists and improves clarity.
这是 Fast/Slow 解决方案的改进，它可以正确处理奇数长度列表并提高清晰度。
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
}
回答by Abhinav
Detecting a loop in a linked list can be done in one of the simplest ways, which results in O(N) complexity using hashmap or O(NlogN) using a sort based approach.
可以通过一种最简单的方法检测链表中的循环，这会导致使用 hashmap 的复杂度为 O(N) 或使用基于排序的方法的复杂度为 O(NlogN)。
As you traverse the list starting from head, create a sorted list of addresses. When you insert a new address, check if the address is already there in the sorted list, which takes O(logN) complexity.
当您从 head 开始遍历列表时，创建一个已排序的地址列表。当您插入一个新地址时，检查该地址是否已经在排序列表中，这需要 O(logN) 复杂度。
