Took 88 ms and the "Accepted Solutions Runtime Distribution" doesn't show any faster Python submissions. The "trick" is to not check all the time whether we have reached the end but to handle it via an exception. "Easier to ask for forgiveness than permission."
The algorithm is of course Tortoise and hare.
def hasCycle(self, head): try: slow = head fast = head.next while slow is not fast: slow = slow.next fast = fast.next.next return True except: return False
Starting fast a step ahead of slow is brilliant. It allows you to use "while slow is not fast:" loop
Because there's only two conditions that the correct code should return False:
- when the linked list is empty.
- when there's no cycle in the linked list. Because the cycle could only happen at the end of the list, this condition also means that the last node in the list has a Null "node.next" property and an assignment such as fast = fast.next.next will fail.
I don't quite get your explanation, especially this:
"the cycle could only happen at the end of the list"?
If there's a cycle, then there's no end.
Anyway, I'd say why I did it is speed. I could use LBYL instead, i.e., use explicit extra tests checking whether next nodes actually exist before trying to access them, but here I chose EAFP. Python will check for access errors anyway, so additionally checking it myself would be a waste of time.
And a meta-reason I did that: Probably the LBYL-way had already been posted, and I don't post when I have nothing new to add to the discussion.
While I absolutely loved your idea, catching all exceptions is considered a bad practice. I think you should at least change it to:
except AttributeError as e:
With this behaviour, you can at least be sure that you are returning False only if the expected exception was raised.
@nirnaor In real life/work that's good, but here and in interviews, personally I think it's unnecessary clutter.
Can you please elaborate on 'except: return False'
I understood that if there is a cycle, then 'return True' gets triggered, but how does the 'except: return False' get triggered?
What if the list looks like 1,1,1,1,1,1,1,1,2,1,1,2,3. In this case, your code will return True at the second value, but we can see this list is not a cycle.
@Root-M7 Nonsense. My code correctly returns
False for that. Looks like you're confusing node values and nodes. It doesn't even matter what the values are, as I'm ignoring them.
How your algorithm will detect a cycle if it forms say five nodes down? If the fifth node pointer value is the same as the head pointer.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.