我的弗洛伊德周期检测算法实现不正确吗？

Question

我有以下代码用于检测链表中的循环：

public Class Node {
    Object data;
    Node next = null;
}
boolean containCycle() {
    boolean retVal = true;
    Node head = this;
    Node slower = head;
    Node faster = head;
    if(faster != null && faster.next != null) {
        faster = faster.next;
    } else {    // there is only one element or zero element
        retVal = false;
    }
    if (faster.next != null) {
        faster = faster.next;
    } else {    // there are only 2 elements
        retVal = false;
    }
    while (slower != faster && slower != null && faster != null) {
        faster = (faster.next != null && faster.next.next != null) ? faster.next.next : null;
        slower = (slower.next != null) ? slower.next : null;
    }
    if (slower == faster) {
        retVal = true;
        System.out.printf("The two pointers meet at: %dn", faster.data);
    } else {
        retVal = false;
    }
    if (retVal) {    // this is the part for detecting where the loop begins
        slower = head;
        while(slower.next != faster.next) {
            slower = slower.next;
            faster = faster.next;
        }
        System.out.println("The cycle starts at: " + slower.data);
    }
    return retVal;
}

这段代码运行良好，直到我真正开始检测循环开始的部分，我在代码中对此进行了注释。不知怎的，这就进入了一个无限循环。

我怀疑这在某种程度上与Java中的传递引用有关？在检测循环时，我是否正在更新head所指的值？我真的没什么主意。请帮忙！

Answer 1

我不知道确切的算法，但您可以使用以下方法来找到汇合点。

让我们将速度较慢和速度较快的节点称为汇合点。

有两个指针，一个从头部开始，另一个从汇合点开始。并计算从头部到集合点需要遍历的节点数量（让我们将此计数称为a）集合点到集合点的下一个节点。（让我们把这个计数称为b）

现在这两个计数中的差|a-b|代表了共同的部分，对吧？（即介于循环开始和慢速和快速交汇点之间的部分）。

所以现在重新开始。重置两个指针，一个指向头部，另一个指向汇合点+1。

例如，如果a>b，则将指针从头移动|a-b|次，否则将指针从会议点移动+1次|a-b|次。

现在把两个指针移到一起，直到它们相遇。

解释的另一种方法

由于您要查找的内容与您有两个链表并且它们在某个节点合并的情况类似，因此您需要识别该节点。您所拥有的只是两个链表的起点。

所以你们从头1开始计数，直到列表的末尾。接下来，你们从头2开始计数，直到列表的末尾。

计算长度的差异。增加较长的路径差异时间。然后开始移动指针，从较短的路径头和diff开始，直到两个指针相遇。

这与你在另一种情况下所做的基本相同。