链表循环

Question

我正在尝试在 python 上编写一个简单的链表循环，但是有一个我无法弄清楚原因的错误。我的代码是这样的：

class ListNode:
   def __init__(self, x):
      self.val = x
      self.next = None
class Solution:
   def hasCycle(self, head: ListNode) -> bool:
      slow=head;
      fast=head;
      while slow and fast:
         slow=slow.next;
         fast=fast.next.next;
         if slow==fast:
             return True
      return False

果然报错

AttributeError: 'NoneType' object has no attribute 'next'

然而，当我尝试使用在线解决方案时：

class Solution:
def hasCycle(self, head: ListNode) -> bool:
    
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            return True
    return False

原来是真的，我不明白为什么会有不同。

慢和快听起来不应该比快和 fast.next 更合理吗？谁能解决我的困惑？

Answer 1

请检查代码

while fast and fast.next:

和

while slow and fast:

Answer 2

错误的原因是循环体有这一行：

fast = fast.next.next

只有当您确定 fast 是 而不是 列表中的最后一个节点时，这才能正常工作。 fast.next 也必须是一个 Node 实例（而不是 None），否则 fast.next.next 转换为 None.next，这显然是无效的。所以为了避免这种情况发生，while 条件也应该验证 fast.next 不是 None.

另一方面，在第一个代码片段中，您检查 slow 是否不是 None，但这是不必要的，因为 slow 永远不会更快到达列表比 fast，所以在 while 条件下关注 fast 就足够了。如果 fast 不是 None，那么你可以确定 slow 也不是 None，因为它永远不会超过 fast.

链表循环

Linked List Cycle

linked-list

python-3.x

singly-linked-list