Python 72ms with easy explanation

  • 0
    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    # = None
    class Solution(object):
        def hasCycle(self, head):
            :type head: ListNode
            :rtype: bool
            if not head or not or not
                return False
            walker, runner = head, head
            while and and
                walker =
                runner =
                if walker == runner:
                    return True
            return False     

    So first I check if I am given anything, or if I am just given a single linked list node or just two. This way I know it is not a cycle and can return false.

    Then I set a walker and a runner to the head, this is following a tortoise and the hair approach.

    In my while loop I am checking if our runner makes it to the end. If it does we know there is no cycle. Inside the while loop, If we find the walker and the runner to equal each other then we know it is a cycle, since the runner is "always" ahead of the walker, if they equal each other, we know that the runner has cycle around and they have crossed paths. We can then return True, knowing there is a cycle.

Log in to reply

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