java - 我的代码有错误吗？ (链表循环)

Question

我目前正在重新学习以前在数据结构方面的一些知识，并决定致力于解决 HackerRank 等问题。我遇到了一个简单的问题，我们必须检测链表中的循环，但我似乎不明白我做错了什么。我查看了其他答案，并理解了它们的语法和逻辑，但似乎找不到我的代码失败的逻辑。

boolean hasCycle(Node head) {

    if (head == null || head.next == null){
        return false;
    }

    Node first = head;
    Node second = head.next;

    while (second != null){
        if (first == second)
        {
            return true;
        }
        first = first.next;
        second = second.next.next;
    }
    return false;
}

Answer 1

据我了解，您的列表可以在任何节点中都有一个圆圈，而不仅仅是第一个节点。您的代码远非解决方案。您可以简化对问题的看法，即必须检查一个节点是否被多次访问。为此，您可以使用像这样的辅助函数

boolean visitedMoreThanOnce(Node head)
{
   if (head.next == null){
        return false;
    }


    Node second = head.next;

    while (second != null){
        if (head == second)
        {
            return true;
        }
        second = second.next;
    }
    return false;
}

那么你的函数可能是

boolean hasCycle(Node head) {

Node first = head;
while (first != null){
    if (visitedMoreThanOnce(first))
    {
        return true;
    }
    first = first.next;
}
return false;
}

请注意，我用你的函数签名解决了这个问题。通过查看问题评论中提供的链接中的问题，似乎 head 应该是一个指针。在这种情况下，您将需要使用 -> 运算符，而不是 。