有人能告诉我证明一个链表包含循环的最好方法吗? 我使用的是一个带有两个指针的算法,一个一步移动缓慢,一个两步移动较快。
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)
一个好的算法如下,它很可能是最好的。不需要复制列表或类似的任何内容,可以在常量空间中完成。
取两个指针并将它们设置为列表的开头。
一次增加一个节点,另两个节点同时增加。
如果列表中的任何点上有循环,则它们必须指向某个点上的同一节点(不包括起点)。显然,如果到达列表的末尾,就没有循环。
编辑:
您的代码,但稍加编辑:
不知道最好的,但我能想到的最简单的是
我会像其他语言一样测试它:
从一开始就遍历列表,通过快速插入和查找将所有访问的元素添加到数据结构(例如集合)中。如果在列表的末尾没有看到任何元素两次,则该列表不是循环的。如果您看到一个元素两次,则该列表是循环的。
如果两者都不是真的,则列表是无限的。:-)
相关问题 更多 >
编程相关推荐