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

Question

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

Answer 1

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

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

Answer 2

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

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

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

编辑 ：

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