Floyd的循环检测算法的实现是否不正确？

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: %d\n", 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|代表共同部分 - 右？ （即在循环的开始和较慢和较快的会合点之间的部分）。

所以，现在再次启动afresh.Reset两个指针，一个头部和其他到会点+ 1

例如，如果a>b，从头部移动指针其他|a-b|时间从会议PIONT + 1 |a-b|移动指针倍。

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

解释这个

既然你在找什么的另一种方式是类似的情况，你有两个链接列表，并合并他们以某个节点，你需要确定节点。 你所拥有的只是两个链表的起点。

所以你从head1开始计数直到列表结束。 接下来你从head2开始计数直到列表结束。

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

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