如何确定循环在链表中发生的位置

Question

链

表中可能存在循环，如何确定循环在链表中发生的位置。

Answer 1

如果有循环，它就不再是链表。这是一个有向图。循环称为循环。

在图形中查找周期的一种方法是遍历列表，标记每个项目。如果您找到已标记的项目，则表示您已经找到了一个循环。

Answer 2

您可以通过保存对节点（例如，列表开头的节点）的引用来判断链表中是否存在循环，并开始迭代列表。如果在某个时候到达列表的末尾（空值），则不存在循环。但是，如果您碰巧再次找到之前保存的同一节点，那么您就知道该列表是循环的。无论哪种方式，请停止迭代。

例如，在 Java 中，此方法将告诉您 Node s 的链表是否是循环的：

public boolean isCircular(Node list) {
    Node current = list;
    while (current != null) {
        if (current.next == list)
            return true;
        current = current.next;
    }
    return false;
}

编辑：

有关在链表中查找任意循环的一般解决方案，请阅读弗洛伊德循环查找算法（又名"龟兔"算法）。在上一篇文章中有一个很好的Java实现。