Python 72ms with easy explanation


  • 0
    K
    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
        def hasCycle(self, head):
            """
            :type head: ListNode
            :rtype: bool
            """
            if not head or not head.next or not head.next.next:
                return False
            
            walker, runner = head, head
            
            while walker.next and runner.next and runner.next.next:
                walker = walker.next
                runner = runner.next.next
                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.