Java 什么是确定单链表是否为循环/循环的有效算法？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1103522/
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
What is an efficient algorithm to find whether a singly linked list is circular/cyclic or not?
提问by harshit
How can I find whether a singly linked list is circular/cyclic or not? I tried to search but couldn't find a satisfactory solution. If possible, can you provide a pseudo-code or Java-implementation?
如何确定单链表是否是循环/循环的？我试图搜索但找不到满意的解决方案。如果可能，您能否提供伪代码或 Java 实现？
For instance:1→ 3→ 5→ 71→ 45→ 7→ 5, where the second 5is actually the third element of the list.
例如：1→ → 3→ 5→ 71→ 45→ 7→ 5，其中第二个5实际上是列表的第三个元素。
采纳答案by Lou Franco
The standard answer is to take two iterators at the beginning, increment the first one once, and the second one twice. Check to see if they point to the same object. Then repeat until the one that is incrementing twice either hits the first one or reaches the end.
标准答案是在开始时取两个迭代器，第一个递增一次，第二个递增两次。检查它们是否指向同一个对象。然后重复，直到增加两次的那个要么击中第一个要么到达终点。
This algorithm finds any circular link in the list, not just that it's a complete circle.
该算法查找列表中的任何圆形链接，而不仅仅是它是一个完整的圆形。
Pseudo-code (not Java, untested -- off the top of my head)
伪代码（不是 Java，未经测试 - 在我的脑海中）
bool hasCircle(List l)
{
Iterator i = l.begin(), j = l.begin();
while (true) {
// increment the iterators, if either is at the end, you're done, no circle
if (i.hasNext()) i = i.next(); else return false;
// second iterator is travelling twice as fast as first
if (j.hasNext()) j = j.next(); else return false;
if (j.hasNext()) j = j.next(); else return false;
// this should be whatever test shows that the two
// iterators are pointing at the same place
if (i.getObject() == j.getObject()) {
return true;
}
}
}
回答by samoz
Start at one node and record it, then iterate through the entire list until you reach a null pointer or the node you started with.
从一个节点开始并记录它，然后遍历整个列表，直到到达一个空指针或您开始的节点。
Something like:
就像是：
Node start = list->head;
Node temp = start->next;
bool circular = false;
while(temp != null && temp != start)
{
if(temp == start)
{
circular = true;
break;
}
temp = temp->next;
}
return circular
This is O(n), which is pretty much the best that you will able to get with a singly linked list (correct me if I'm wrong).
这是 O(n)，这几乎是单向链表所能得到的最好的结果（如果我错了，请纠正我）。
Or to find any cycles in the list (such as the middle), you could do:
或者要查找列表中的任何循环（例如中间），您可以执行以下操作：
Node[] array; // Use a vector or ArrayList to support dynamic insertions
Node temp = list->head;
bool circular = false;
while(temp != null)
{
if(array.contains(temp) == true)
{
circular = true;
break;
}
array.insert(temp);
temp = temp->next;
}
return circular
This will be a little bit slower due to the insertion times of dynamic arrays.
由于动态数组的插入时间，这会慢一点。
回答by leo
@samoz has in my point of view the answer! Pseudo code missing. Would be something like
在我看来，@samoz 给出了答案！伪代码丢失。会像
yourlist is your linked list
yourlist 是你的链表
allnodes = hashmap
while yourlist.hasNext()
node = yourlist.next()
if(allnodes.contains(node))
syso "loop found"
break;
hashmap.add(node)
sorry, code is very pseudo (do more scripting then java lately)
抱歉，代码非常伪（最近比 java 编写更多脚本）
回答by leppie
Use the Tortoise-Hare algorithm.
使用龟兔算法。
回答by Markus Lausberg
Here is a nice site on which the different solutions can copied.
这是一个不错的站点，可以在其上复制不同的解决方案。
This is the winner on that site
这是该网站的获胜者
// Best solution
function boolean hasLoop(Node startNode){
Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
if (slowNode == fastNode1 || slowNode == fastNode2) return true;
slowNode = slowNode.next();
}
return false;
}
This solution is "Floyd's Cycle-Finding Algorithm" as published in "Non-deterministic Algorithms" by Robert W. Floyd in 1967. It is also called "The Tortoise and the Hare Algorithm".
该解决方案是 Robert W. Floyd 于 1967 年在“Non-deterministic Algorithms”中发表的“Floyd's Cycle-Finding Algorithm”。它也被称为“The Tortoise and the Hare Algorithm”。
回答by ajay
It will never terminate from the loop, it can also be done in following solution:
它永远不会从循环中终止，也可以在以下解决方案中完成：
bool hasCircle(List l)
{
Iterator i = l.begin(), j = l.begin();
while (true) {
// increment the iterators, if either is at the end, you're done, no circle
if (i.hasNext()) i = i.next(); else return false;
// second iterator is travelling twice as fast as first
if (j.hasNext()) j = j.next(); else return false;
if (j.hasNext()) j = j.next(); else return false;
// this should be whatever test shows that the two
// iterators are pointing at the same place
if (i.getObject() == j.getObject()) {
return true;
}
if(i.next()==j)
break;
}
}
回答by Batman
I you count your Nodes and get to the *head again.
我你计算你的节点并再次到达*头。
回答by Mark Byers
A simple algorithm called Floyd's algorithmis to have two pointers, a and b, which both start at the first element in the linked list. Then at each step you increment a once and b twice. Repeat until you either reach the end of the list (no loop), or a == b (the linked list contains a loop).
一种称为Floyd 算法的简单算法是有两个指针 a 和 b，它们都从链表的第一个元素开始。然后在每一步你增加一次 a 和 b 两次。重复直到到达列表的末尾（无循环）或 a == b（链表包含循环）。
Another algorithm is Brent's algorithm.
另一种算法是布伦特算法。
回答by Brent Writes Code
Three main strategies that I know of:
我知道的三个主要策略：
Starting traversing the list and keep track of all the nodes you've visited (store their addresses in a map for instance). Each new node you visit, check if you've already visited it. If you've already visited the node, then there's obviously a loop. If there's not a loop, you'll reach the end eventually. This isn't great because it's O(N) space complexity for storing the extra information.
The Tortoise/Hare solution. Start two pointers at the front of the list. The first pointer, the "Tortoise" moves forward one node each iteration. The other pointer, the "Hare" moves forward two nodes each iteration. If there's no loop, the hare and tortoise will both reach the end of the list. If there is a loop, the Hare will pass the Tortoise at some point and when that happens, you know there's a loop. This is O(1) space complexity and a pretty simple algorithm.
Use the algorithm to reverse a linked list. If the list has a loop, you'll end up back at the beginning of the list while trying to reverse it. If it doesn't have a loop, you'll finish reversing it and hit the end. This is O(1) space complexity, but a slightly uglier algorithm.
开始遍历列表并跟踪您访问过的所有节点（例如将它们的地址存储在地图中）。您访问的每个新节点，检查您是否已经访问过它。如果您已经访问过该节点，那么显然存在一个循环。如果没有循环，你最终会到达终点。这不是很好，因为存储额外信息的空间复杂度为 O(N)。
乌龟/野兔解决方案。在列表的前面开始两个指针。第一个指针“乌龟”每次迭代向前移动一个节点。另一个指针“野兔”每次迭代向前移动两个节点。如果没有循环，兔子和乌龟都会到达列表的末尾。如果有一个循环，兔子会在某个时候超过乌龟，当这种情况发生时，你就知道有一个循环。这是 O(1) 空间复杂度和一个非常简单的算法。
使用该算法来反转链表。如果列表有一个循环，您将在尝试反转它时返回到列表的开头。如果它没有循环，您将完成反转并到达终点。这是 O(1) 空间复杂度，但算法略显丑陋。
回答by Asha
A algorithm is:
一个算法是：
- Store the pointer to the first node
- Traverse through the list comparing each node pointer to this pointer
- If you encounter a NULL pointer, then its not circularly linked list
- If you encounter the first node while traversing then its a circularly linked list
- 存储指向第一个节点的指针
- 遍历链表，比较每个节点指针和这个指针
- 如果遇到 NULL 指针，则它不是循环链表
- 如果您在遍历时遇到第一个节点，则它是一个循环链表
