检测链表中的循环

Question

如何检测循环在一个链表只使用单个指针?(不需要慢速和快速指针(野兔和乌龟))

Answer 1

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

在每个节点检查该节点是否已经存在于哈希表中。如果是这样，你就找到了一个循环。否则，将其添加到哈希表中，并继续到下一个节点。

Answer 2

Brent的算法在这里显然是最好的:对于无循环的列表，它只需访问列表一次，而Floyd的龟兔式算法需要重新访问一半的节点。对于带有循环的列表，它在循环中的"旋转"时间永远不会超过Floyd;在最好的情况下只需要一个周期，而弗洛伊德需要很多周期。考虑一个长无循环序列，后面跟着一个长度为1的循环。在这种情况下，布伦特的最佳情况是在一次访问循环后检测循环——即访问每个节点一次;而Floyd平均需要访问每个节点三次。

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

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