识别列表中的循环或递归

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,这意味着检测到了循环.

由于我的答案有所改变,我想说还有其他解决方案.在这个主题中已经指出的另一个是乌龟和野兔算法.您可以在此主题或此Wiki页面上找到有关该主题的更多信息.

Answer 2

您应该有两个EntityNode对象.两者都从Node1开始.让第一个对象向下移动两个节点,第二个向下移动一个节点.重复此操作直到您到达结尾(没有循环)或两个对象在同一节点相遇(有一个循环).

对于你的例子:

n1:Node1,n2:Node1

n1:Node3,n2:Node2

n1:Node5,n2:Node3

n1:Node4,n2:Node4 - >循环!!

对于伪代码:

while (n1.nextNode isn't null):
    n1 = n1.nextNode.nextNode
    n2 = n2.nextnode
    if (n1 equals n2): return 'there is a loop!'