CODEWITHSUNDEEP
python-3.xlinked-listsingly-linked-list
lok cheng
lok cheng

Reputation: 15

Linked List Cycle

I am trying to write a simple linked list cycle on python, however there is a bug I couldn't figure out why. My code is something like this:

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

It indeed comes with an error

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

However when I try with the online solution which is:

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

It turns out to be true, I don't understand why there is a different.

Shouldn't slow and fast sound more reasonable than fast and fast.next? Could anyone solve my confusion?

Upvotes: 0

Views: 434

Answers (2)

trincot
trincot

Reputation: 350766

The reason of the error is that the body of the loop has this line:

fast = fast.next.next

This can only work without error when you are sure that fast is not the last node in the list. fast.next must also be a Node instance (and not None), as otherwise fast.next.next translates to None.next, which obviously is invalid. So to avoid this from happening, the while condition should also verify that fast.next is not None.

On the other hand, in the first code snippet you check whether slow is not None, but that is unnecessary, because slow will never arrive faster at the end of the list than fast, so it is enough to focus on fast in the while condition. If fast is not None, then you can be sure that slow is not None either, as it never surpasses fast.

Upvotes: 0

youDaily
youDaily

Reputation: 1384

please check the code

while fast and fast.next:

and

while slow and fast:

Upvotes: 0

Related Questions