假设您在Java中有一个链表结构。它由节点组成:
class Node {
Node next;
// some user data
}
每个节点都指向下一个节点，除了最后一个节点，它的next为空。假设有一种可能性，列表可以包含一个循环-即最后的节点，而不是有一个空值，有一个引用到列表中它之前的一个节点。
最好的写作方式是什么
boolean hasLoop(Node first)
如果给定的节点是带有循环的列表的第一个，则返回true，否则返回false ?你怎么能写出一个常数的空间和合理的时间呢?
下面是一个带有循环的列表的图片:
当前回答
乌龟和兔子
看看波拉德的算法。这不是完全相同的问题，但也许你会理解其中的逻辑，并将其应用于链表。
(如果你很懒，你可以看看周期检测——看看关于乌龟和兔子的那部分。)
这只需要线性时间和2个额外的指针。
在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;
}
(大多数解决方案不会同时检查next和next。接下来是null。此外，因为乌龟总是在后面，你不需要检查它是否为空——兔子已经检查过了。)
其他回答
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;
}
下面的方法可能不是最好的——它是O(n²)。然而，它应该有助于完成工作(最终)。
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++;
}
boolean hasCycle(Node head) {
boolean dec = false;
Node first = head;
Node sec = head;
while(first != null && sec != null)
{
first = first.next;
sec = sec.next.next;
if(first == sec )
{
dec = true;
break;
}
}
return dec;
}
使用上述函数在java中检测linkedlist中的循环。
你可以使用弗洛伊德的周期寻找算法，也被称为乌龟和野兔算法。 其思想是对列表有两个引用，并以不同的速度移动它们。一个向前移动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;
}
}
在这个上下文中，到处都有文本材料的加载。我只是想张贴一个图表表示，真正帮助我掌握概念。
当快、慢在点p相遇时，
快速行进的距离= a+b+c+b = a+2b+c
慢行距离= a+b
因为快的比慢的快2倍。 所以a+2b+c = 2(a+b)然后得到a=c。
因此，当另一个慢指针再次从头部运行到q时，同时，快速指针将从p运行到q，因此它们在q点会合。
public ListNode detectCycle(ListNode head) {
if(head == null || head.next==null)
return null;
ListNode slow = head;
ListNode fast = head;
while (fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
/*
if the 2 pointers meet, then the
dist from the meeting pt to start of loop
equals
dist from head to start of loop
*/
if (fast == slow){ //loop found
slow = head;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
