假设您在Java中有一个链表结构。它由节点组成:

class Node {
    Node next;
    // some user data
}

每个节点都指向下一个节点,除了最后一个节点,它的next为空。假设有一种可能性,列表可以包含一个循环-即最后的节点,而不是有一个空值,有一个引用到列表中它之前的一个节点。

最好的写作方式是什么

boolean hasLoop(Node first)

如果给定的节点是带有循环的列表的第一个,则返回true,否则返回false ?你怎么能写出一个常数的空间和合理的时间呢?

下面是一个带有循环的列表的图片:


当前回答

//链表查找循环函数

int findLoop(struct Node* head)
{
    struct Node* slow = head, *fast = head;
    while(slow && fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
            return 1;
    }
 return 0;
}

其他回答

这是我在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;
}
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)

我不确定这个答案是否适用于Java,但我仍然认为它属于这里:

当我们在现代体系结构中使用指针时,我们可以期望它们是CPU字对齐的。对于64位体系结构,这意味着指针的前3位始终为零。这让我们可以使用这个内存来标记我们已经见过的指针,通过对它们的第一个比特写入1。

如果我们遇到一个指针,它的第一个位已经写了1,那么我们已经成功地找到了一个循环,之后我们需要再次遍历结构,并将这些位屏蔽掉。完成了!

这种方法被称为指针标记,它在低级编程中被过度使用,例如Haskell在一些优化中使用它。

用户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;
    }
}