// 解法1: 哈希表
// 扫描整个链表，扫描的过程中看当前节点有没有被之前访问过，访问过的话就是有环。
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == NULL) {
            return NULL;
        }

        unordered_set<ListNode *> set;
        for (auto cur = head; cur; cur = cur->next) {
            if (set.find(cur) != set.end()) {
                return true;
            }
            set.insert(cur);
        }

        return false;
    }
};

// 最优解：双指针算法，快慢指针
// 1. 快指针每次走两步，慢指针每次走一步。
// 2. 如果快慢指针能够相遇，则说明有环，否则没环。
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == NULL || head->next == NULL) {
            return false;
        }

        ListNode* slow = head;
        ListNode* fast = head->next;

        while(fast != slow) {
            if(fast == NULL || fast->next == NULL) {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }

        return true;
    }
};