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

问题描述

有人可以让我知道证明链表包含循环的最佳方式吗？
我正在使用一个具有两个指针的算法，一个是缓慢移动一个步骤，一个是两步更快地移动。

  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 
返回头
 
 def is_circular（head）：
 slow = head 
 fast = head 
 while True：
 slow = slow.next 
 fast = fast.next.next 
 print slow.value，fast.value 
如果slow.value == fast.value：
 return True 
 elif slow is fast：
 return False 
 
如果__name__ ==__main__：
 node = create_list（）
 print i s_circular（node）
  

解决方案

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

取两个指针并将其设置为列表的开头。一个一个增加一个节点，一次增加另一个节点。

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

编辑：

你的代码，但是略微修改：

  def is_circular（head）：
 
 slow = head 
 fast = head 
 
 while fast！= None：
 slow = slow.next 
 
如果fast.next！=无：
 fast = fast.next。下一个
 else：
 return 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 fast.next != None:
              fast = fast.next.next
         else:
              return False

         if slow is fast:
              return True

    return False

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