题解 | #牛牛队列成环#

知识点：

• 单链表的环检测。
• 哈希表的应用。

题意分析：

题目描述了一个农场里的牛队列，每头牛都有一个唯一的编号，编号范围在 [-105, 105] 内。每头牛都有一个指针指向它后面的一头牛，但有些顽皮的牛可能会指向它们前面的某一头牛，从而形成一个环。要求判断给定的链表是否有环。

时间复杂度：

假设链表的长度为 N。

在代码中，我们使用了一个哈希集合（unordered_set）来记录已经访问过的节点的编号。在最坏情况下，所有的节点都不构成环，我们需要遍历所有的节点一次。所以时间复杂度为 O(N)。

代码分析：

代码使用了一个 unordered_set 来记录已经访问过的节点的编号。然后，通过遍历链表的每个节点，检查当前节点的编号是否已经存在于集合中。如果存在，说明之前已经访问过，说明存在环，返回 true。否则，将当前节点的编号加入集合中，然后继续遍历下一个节点。最后，如果遍历完整个链表都没有发现环，则返回 false。

class Solution {
public:
    bool hasCycle(ListNode* head) {
        std::unordered_set<int> visitedIndices;
        
        while (head) {
            if (visitedIndices.count(head->val)) {
                return true;
            }
            visitedIndices.insert(head->val);
            head = head->next;
        }
        
        return false;
    }

private:
    /**
     * 生成一个随机数作为链表节点的值
     */
    int generateRandomValue() {
        return rand() % 100;
    }

    /**
     * 创建一个带有指定值的链表节点
     */
    ListNode* createNodeWithValue(int value) {
        ListNode* node = new ListNode(value);
        return node;
    }
};