最快的证明链表的方法是圆形的？在python [英] Fastest way to prove linked list is circular ? in python

问题描述

可能有人请让我知道，证明一个链表包含循环最好的方法是什么？ 我使用的算法有两个指针，一个是移动的一个步骤缓慢，一个是用两个步骤移动速度。

 类节点（对象）：
    高清__init __（个体经营，价值，接下来=无）：
        self.next =下一个
        self.value =价值
高清create_list（）：
    最后=节点（8）
    头=节点（7，最后）
    头=节点（6头）
    头=节点（5头）
    头=节点（4头）
    头=节点（3头）
    头=节点（2头）
    头=节点（1头）
    last.next =头
    返回头

高清is_circular（头）：
    慢=头
    快=头
    而真正的：
        慢= slow.next
        快= fast.next.next
        打印slow.value，fast.value
        如果slow.value == fast.value：
            返回True
        ELIF慢是快：
            返回False

如果__name__ ==__main__：
    节点= create_list（）
    打印is_circular（节点）
 

解决方案

一个很好的算法如下，它很可能是最好的。你并不需要复制该列表或任何东西，这样，可以在不断的空间完成。

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

让一个增量一次一个节点，并在同一时间其他两个节点。

如果有环路在列表中的任何一点上，他们将必须指向相同的节点在某一点（不包括起点）。很明显，如果到达列表的末尾，不存在环

修改：
您的code，但可能有一点不同：

 高清is_circular（头）：

     慢=头
     快=头

     而快=无！
         慢= slow.next

         如果慢是快：
              返回True

         如果fast.next =无！
              快= fast.next.next
         其他：
              返回False

         如果慢是快：
              返回True

    返回False
 

Could someone please let me know the best way to prove a linked list contains a loop? I am using an algorithm with two pointer, one is moving slow with one steps and one is moving faster with two steps.

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)

解决方案

A good algorithm is as follows, it may very well be the best. You do not need to copy the list or anything, like that, it can be done in constant space.

Take two pointers and set them to the beginning of the list.

Let one increment one node at a time and the other two nodes at a time.

If there is a loop at any point in the list, they will have to be pointing to the same node at some point (not including the starting point). Obviously if you reach the end of the list, there is no loop.

EDIT:
Your code, but slightly edited:

def is_circular(head):

     slow = head
     fast = head

     while fast != None:
         slow = slow.next

         if slow is fast:
              return True

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

         if slow is fast:
              return True

    return False

这篇关于最快的证明链表的方法是圆形的？在python的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！