Except-ionally fast Python


  • 70

    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

  • 6
    S

    Oh, man, I am really learning from you!


  • 0
    This post is deleted!

  • 1
    E

    Starting fast a step ahead of slow is brilliant. It allows you to use "while slow is not fast:" loop


  • 0
    R

    not so sure why using try and except here, can u explain? thanks


  • 1
    S

    Because there's only two conditions that the correct code should return False:

    1. when the linked list is empty.
    2. 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.

  • 1

    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.


  • 2
    N

    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.


  • 0

    @nirnaor In real life/work that's good, but here and in interviews, personally I think it's unnecessary clutter.


  • 0
    C

    Oh man, you are really smart. blow my mind!


  • 0
    A

    @StefanPochmann said in Except-ionally fast Python:

    except:
    return False

    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?


  • 0
    E

    Really appreciated. Very wise solution and unexpected fast.


  • 0

    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.


  • 0

    @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.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.