0

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

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检测循环时引用的值？我真的没有想法。请帮忙！

4

1 回答 1

0

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

让我们将越来越慢的节点称为会合点。

有两个指针，一个从头部开始，另一个从会合点开始。并计算您需要从头到会点遍历多少个节点（让我们将此计数称为a）以及会合点的下一个节点到会合点。（让我们称之为计数 b）

现在|a-b|这两个计数的差异代表了共同的部分-对吗？（即循环开始和越来越快的交汇点之间的部分）。

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

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

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

另一种解释方式

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

因此，您从 head1 开始并数到列表末尾。接下来，您从 head2 开始并数到列表末尾。

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

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

于 2013-02-21T05:21:33.463 回答