假设您在Java中有一个链表结构。它由节点组成:
class Node {
Node next;
// some user data
}
每个节点都指向下一个节点，除了最后一个节点，它的next为空。假设有一种可能性，列表可以包含一个循环-即最后的节点，而不是有一个空值，有一个引用到列表中它之前的一个节点。
最好的写作方式是什么
boolean hasLoop(Node first)
如果给定的节点是带有循环的列表的第一个，则返回true，否则返回false ?你怎么能写出一个常数的空间和合理的时间呢?
下面是一个带有循环的列表的图片:
当前回答
这段代码经过优化，将比选择的最佳答案更快地产生结果。这段代码避免了进入一个非常长的追逐向前和向后节点指针的过程，如果我们遵循'最佳答案'方法，在以下情况下将发生这种情况。看一下下面的演练，你就会明白我想说的是什么。然后通过下面给出的方法来观察问题，并测量否。为了找到答案所采取的步骤。
1 - > 2 - > 9 - > 3 ^ -- -- -- -- -- -- -- - ^
代码如下:
boolean loop(node *head)
{
node *back=head;
node *front=head;
while(front && front->next)
{
front=front->next->next;
if(back==front)
return true;
else
back=back->next;
}
return false
}
其他回答
我不确定这个答案是否适用于Java，但我仍然认为它属于这里:
当我们在现代体系结构中使用指针时，我们可以期望它们是CPU字对齐的。对于64位体系结构，这意味着指针的前3位始终为零。这让我们可以使用这个内存来标记我们已经见过的指针，通过对它们的第一个比特写入1。
如果我们遇到一个指针，它的第一个位已经写了1，那么我们已经成功地找到了一个循环，之后我们需要再次遍历结构，并将这些位屏蔽掉。完成了!
这种方法被称为指针标记，它在低级编程中被过度使用，例如Haskell在一些优化中使用它。
// 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;
}
}
}
这是我在java中的解决方案
boolean detectLoop(Node head){
Node fastRunner = head;
Node slowRunner = head;
while(fastRunner != null && slowRunner !=null && fastRunner.next != null){
fastRunner = fastRunner.next.next;
slowRunner = slowRunner.next;
if(fastRunner == slowRunner){
return true;
}
}
return false;
}
用户unicornaddict上面有一个很好的算法，但不幸的是，它包含一个错误，用于奇数长度>= 3的非循环列表。问题是，快的可能会在列表结束之前“卡住”，慢的会赶上它，然后就会(错误地)检测到循环。
这是修正后的算法。
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;
}
}
这段代码经过优化，将比选择的最佳答案更快地产生结果。这段代码避免了进入一个非常长的追逐向前和向后节点指针的过程，如果我们遵循'最佳答案'方法，在以下情况下将发生这种情况。看一下下面的演练，你就会明白我想说的是什么。然后通过下面给出的方法来观察问题，并测量否。为了找到答案所采取的步骤。
1 - > 2 - > 9 - > 3 ^ -- -- -- -- -- -- -- - ^
代码如下:
boolean loop(node *head)
{
node *back=head;
node *front=head;
while(front && front->next)
{
front=front->next->next;
if(back==front)
return true;
else
back=back->next;
}
return false
}
