检测链表中的循环

Question

如何仅使用单个指针来检测链表中的循环？ （不想要慢指针和快指针（兔子和乌龟））

Answer 1

如果您不介意额外的 O(N) 内存，您可以使用 hashtable 来存储沿着链表前进时访问过的节点。

在每个节点上，您检查该节点是否已存在于哈希表中。如果是这样，您就发现了一个循环。否则，您将其添加到哈希表中并移至下一个节点。

Answer 2

Brent 算法 显然是最好的：对于无循环列表，它只需访问列出一次，而弗洛伊德的龟兔赛跑则需要重新访问一半的节点。对于带有循环的列表，它在循环中“旋转”的时间永远不会比 Floyd 长；在最好的情况下只需要一个周期，而弗洛伊德则需要多个周期。考虑一个长的无循环序列，后面跟着一个长度为 1 的循环。在这种情况下，Brent 的最佳情况是在一次循环访问后检测循环 - 因此每个节点恰好访问一次；而Floyd平均需要访问每个节点3次。

基本思想是访问链表并将当前节点的指针与一个已经访问过的节点进行比较。也就是说，每个访问节点进行一次指针比较。指针按照简单的逻辑不时更新。

Answer 3

如果您的节点由值和指向下一个节点的指针组成，则可以使用列表创建指向第一个节点的指针。您可以在每个节点上检查指针是否与指向第一个节点的指针具有相同的值。

Answer 4

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head:
            return False
        current_node = head
        seen = set()
        while (current_node not in seen):
            # This means there is a tail
            if current_node.next == None:
                return False
            seen.add(current_node)
            current_node = current_node.next
        # current_node would be the start of the cycle
        return True