题解 | #牛牛队列成环#

牛牛队列成环

https://www.nowcoder.com/practice/38467f349b3a4db595f58d43fe64fcc7

知识点:

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

题意分析:

题目描述了一个农场里的牛队列,每头牛都有一个唯一的编号,编号范围在 [-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;
    }
};

全部评论

相关推荐

每晚夜里独自颤抖:要求太多的没必要理
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务