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

标签 python algorithm data-structures linked-list

<分区>

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

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)

最佳答案

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

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

一次递增一个节点，一次递增另外两个节点。

如果列表中的任何一点都存在循环，则它们必须在某个点(不包括起始点)指向同一个节点。显然，如果您到达列表的末尾，则没有循环。

编辑:
您的代码，但略有编辑:

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

关于python - 证明链表是循环的最快方法？在 python ，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20353835/

上一篇：python - 为什么这会发生在 Python 中？它与列表可变性有关吗？

下一篇：python - 能否在python或Matlab中用Pyplot绘制数字波形图？

python - 您可以在python的列表理解中使用ifinstance吗？

python - 如何拆分一个元素并用python替换列表中的两个部分

python - 更改 scikit learn 中的数字格式

c# - 关于语法错误的子串，这个事实是真的吗？

c# - 如何检查字节数组是否包含另一个数组

python - 优化 julia one-liner 使其与 python 一样快

algorithm - 通过浮点或双域算法索引

c++ - 后缀范围 c++

c - 如何在C中给定深度修剪树数据结构