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

Follow up:
Can you solve it without using extra space?

Solution:

Method 1. Use a hash table to store the addresses visited, if there is duplicated addresses, then a cycle is found, otherwise there is no cycle.

Method 2. Fast and slow pointers.

Notice that we use the fast->next != NULL and fast->next->next != NULL to be the condition for the while loop. The idea is to make sure that the furthest at each step to be valid. However, when considering fast->next->next, chances are fast->next is already null so we have to consider this first.

Also this problem is like you have two constraints to satisfy. You can make one of them to be the condition of the while loop, the other condition inside the while loop to return.

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        if (fast == NULL || fast->next == NULL || fast->next->next == NULL)
            return false;
        while (fast->next != NULL && fast->next->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            if (fast == slow) return true;
        }
        return false;
    }
};