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