Linked List Cycle

Question

Given a linked list, determine if it has a cycle in it.

Thoughts

快慢指针，快的速度是慢的两倍，如果有cycle,那快的最终会追上慢的并且不会有终点

Solution

class Solution:
    """
    @param head: The first node of the linked list.
    @return: True if it has a cycle, or false
    """
    def hasCycle(self, head):
        # write your code here
        if not head or not head.next:
            return False
        slow = head
        fast = head
        """
        快的指针要跳两个，所以要判定当前的和next
        如果有None的，说明有中点没有cycle
        """
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False