假设您在Java中有一个链表结构。它由节点组成:
class Node {
Node next;
// some user data
}
每个节点都指向下一个节点，除了最后一个节点，它的next为空。假设有一种可能性，列表可以包含一个循环-即最后的节点，而不是有一个空值，有一个引用到列表中它之前的一个节点。
最好的写作方式是什么
boolean hasLoop(Node first)
如果给定的节点是带有循环的列表的第一个，则返回true，否则返回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
}
其他回答
你可以使用弗洛伊德的周期寻找算法，也被称为乌龟和野兔算法。 其思想是对列表有两个引用，并以不同的速度移动它们。一个向前移动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;
}
}
// 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;
}
}
}
检测链表中的循环可以用最简单的方法之一来完成，使用hashmap会导致O(N)复杂度，使用基于排序的方法会导致O(NlogN)复杂度。
当您从head开始遍历列表时，创建一个已排序的地址列表。当您插入一个新地址时，检查该地址是否已经在已排序的列表中，这需要O(logN)复杂度。
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中的循环。
你也可以使用上述答案中所建议的弗洛伊德乌龟算法。
该算法可以检查单链表是否具有闭合循环。 这可以通过迭代带有两个移动速度不同的指针的列表来实现。通过这种方式，如果存在一个循环，两个指针将在未来的某个时间点相遇。
请随意查看我关于链表数据结构的博客文章，在那里我还包含了一个用java语言实现上述算法的代码片段。
问候,
安德烈亚斯 （@xnorcode）
