证明链表是循环的最快方法？在python中

Question

有人能告诉我证明一个链表包含循环的最好方法吗？ 我使用的是一个带有两个指针的算法，一个一步移动缓慢，一个两步移动较快。

class Node(object):
    def __init__(self, value, next=None):
        self.next=next
        self.value=value
def create_list():
    last = Node(8)
    head = Node(7, last)
    head = Node(6, head)
    head = Node(5, head)
    head = Node(4, head)
    head = Node(3, head)
    head = Node(2, head)
    head = Node(1, head)
    last.next = head
    return head

def is_circular(head):
    slow = head
    fast = head
    while True:
        slow = slow.next
        fast = fast.next.next
        print slow.value, fast.value
        if slow.value == fast.value:
            return True
        elif slow is fast:
            return False

if __name__ == "__main__":
    node = create_list()
    print is_circular(node)

Answer 1

一个好的算法如下，它很可能是最好的。不需要复制列表或类似的任何内容，可以在常量空间中完成。

取两个指针并将它们设置为列表的开头。

一次增加一个节点，另两个节点同时增加。

如果列表中的任何点上有循环，则它们必须指向某个点上的同一节点（不包括起点）。显然，如果到达列表的末尾，就没有循环。

编辑：
您的代码，但稍加编辑：

def is_circular(head):

     slow = head
     fast = head

     while fast != None:
         slow = slow.next

         if fast.next != None:
              fast = fast.next.next
         else:
              return False

         if slow is fast:
              return True

    return False

Answer 2

不知道最好的，但我能想到的最简单的是

>>> import json
>>> l = []
>>> l.append(l)
>>> json.dumps(l)
Traceback (most recent call last):
  ...
ValueError: Circular reference detected

Answer 3

我会像其他语言一样测试它：

从一开始就遍历列表，通过快速插入和查找将所有访问的元素添加到数据结构（例如集合）中。如果在列表的末尾没有看到任何元素两次，则该列表不是循环的。如果您看到一个元素两次，则该列表是循环的。

如果两者都不是真的，则列表是无限的。：-）