弗洛伊德的循环检测算法：说明如何在链表中找到循环的起始节点？☆☆☆

回答：

这是用于循环检测的弗洛伊德算法。一旦发现一个节点是周期的一部分，如何找到周期的起点？

在弗洛伊德算法的第一部分中，野兔为乌龟的每一步移动了两步。如果乌龟和野兔相遇过，那就有一个循环，并且相遇点是循环的一部分，但不一定是循环中的第一个节点。
乌龟和野兔相遇后，让我们将乌龟放回列表的开头，然后将野兔保持在它们相遇的位置（距离周期开始k步）。如果我们让他们以相同的速度（1步两种），将他们曾经再次见面将是周期开始时的第一次。

另一个要提到的解决方案是Hash Map：

遍历节点列表。
对于遇到的每个节点，将其添加到身份哈希映射中
如果该节点已存在于身份映射中，则该列表具有环形链接，并且知道此冲突之前的节点（在移动之前进行检查或保留“最后一个节点”）

实现方式：

JAVA

public ListNode getLoopStartingPoint(ListNode head) {
    boolean isLoopExists = false;
    ListNode slowPtr = head, fastPtr = head;

    while (!Objects.isNull(fastPtr) && !Objects.isNull(fastPtr.getNext())) {
        slowPtr = slowPtr.getNext();
        fastPtr = fastPtr.getNext().getNext();
        if (slowPtr == fastPtr) {
            isLoopExists = true;
            break;
        }
    }

    if (!isLoopExists) return null;

    slowPtr = head;
    while (slowPtr != fastPtr) {
        slowPtr = slowPtr.getNext();
        fastPtr = fastPtr.getNext();
    }
    return slowPtr;
}

常见问题FAQ