证明链表的最快方式是循环？在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