题解 | 牛牛队列成环

语言： C++

知识点： 链表， 快慢指针 / 哈希表

方法一： 判断链表中是否有环可以使用快慢指针解决，具体方法是：定义一个快指针fast和一个慢指针slow，fast每次走两个节点，slow每次走一个节点，若链表中有环，则当两个指针都进入环中之后，由于slow是逐个节点遍历的，而fast的遍历速度又快于slow，因此fast一定会在套了slow若干圈后与slow相遇，所以由此可以通过判断遍历过程中两指针是否会相遇（本题编号唯一可以判断指针处编号是否相同）来判断是否有环。同时注意遍历的结束条件需要判断fast指针及其next域（因为每次走两个节点）是否为空（本题由于需要比较指针处的值，因此还需加上fast->next->next是否为空的判断），若fast可以遍历到空则表示链表无环。

代码实现（快慢指针）：

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return bool布尔型
     */
    bool hasCycle(ListNode* head) {
        ListNode* fast = head, * slow = head;
        while(fast && fast->next && fast->next->next) // fast若走到空则表示无环，同时还需注意指针越界问题
        {
            fast = fast->next->next; // 快指针每次走两个节点
            slow = slow->next; // 慢指针每次走一个节点
            if(fast->val == slow->val)
            {
                return true;
            }
        }
        return false;
    }
};

方法二： 本题由于编号唯一，也可以遍历链表同时使用哈希表记录出现的编号，若遇到之前出现过的编号则表示有环返回true，若遍历完后没有重复则表示无环返回false。该方法只适用于编号不重复情况，若有重复则需添加标记位再判断标记位是否重复访问。

代码实现（哈希表）：

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return bool布尔型
     */
    bool hasCycle(ListNode* head) {
        ListNode* p = head;
        unordered_set<int> st; // 存储出现的编号
        while(p)
        {
            if(st.count(p->val))
            {
                return true; // 出现重复编号则有环
            }
            st.emplace(p->val);
            p = p->next;
        }
        return false; // 遍历结束后无重复则无环
    }
};