java - 识别列表中的循环或递归

Question

我想为节点的以下结构识别列表中的循环或递归。我怎样才能识别相同的？

public class EntityNode {
    private EntityNode nextNode; // Points to the next node
}

例子，

Node1 -> Node2 -> Node3 -> Node4 -> Node5 -> Node6 -> Node4

在这里，你可以看到Node6指向了Node4，这里就出现了循环或者递归，我的代码会进入无穷大。那么如果我想找出具有最佳性能水平的此类场景怎么办？

Answer 1

这其实是我听过几次的面试题。虽然我从未尝试实现任何类型的循环检测，但大多数面试官似乎喜欢的答案是遍历列表并将访问过的节点存储在哈希表中。如果您在存储到表中时遇到冲突，那么您的列表中就有一个循环。

编辑:为了尝试为该示例提供一些代码，我可能会尝试这样做(假设您有某种 LinkedList<EntityNode> 对象)。我将其更新为使用 HashSet 而不是 HashMap，因此它更直接(正如 PM 77-1 所指出的)。

public bool detectLoop(LinkedList<EntityNode> list)
{
    Set<EntityNode> nodeSet = new HashSet<EntityNode>();
    EntityNode curNode = list.getHead();
    boolean loopDetected = false;

    if(curNode != null)
    {
        while(curNode.getNextNode() != null && !loopDetected)
        {
            cureNode = curNode.getNextNode();
            loopDetected = !nodeSet.add(curNode);
        }
    }

    return loopDetected;
}

我还没有机会对此进行测试，但这应该可行。原因是 add() HashSet 的方法返回 true if this set did not already contain the specified element .因此，如果集合中已经存在一个 EntityNode，它将返回 false，这意味着检测到一个循环。

由于我的回答已经开始，我想说还有其他解决方案。此线程中指出的另一个是乌龟和野兔算法。您可以在 this thread 中找到更多相关信息。或在 this wiki page .