题解 | #牛牛队列成环#

考察的知识点：与链表有关的题基本都是插入，删除，交换顺序等，解决这些问题通常将链表的指针进行修改。

问题分析：首先说一下这道题和链表中是否有环的区别：1. 其中链表有环，是最后结点的next指向前面的某个结点，构成一个环状；2.而这道题最后一个节点的next指向空，是没有环状结构的，但是前面结点中的值有的是重复的（每只牛编号唯一），这些重复的值可以构成“环状”，可以说是将值模拟成环状。

解题思路：链表中是否有环，通常用快慢指针来解决，慢指针走一步，快指针走两步，当有环时，快慢指针必相遇，**为什么必相遇？** 假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。**而且相遇之前这个环最对被遍历两边。** 所以上面这道题就可以用快慢指针来解决，遍历重复数据最多将遍历两遍。

本题解析所用的编程语言：c++

代码如下：

bool hasCycle(ListNode* head)
{
    // write code here
    ListNode* slow = head, * fast = head->next;
    while (fast != nullptr && fast->next != nullptr)
    {
        if (slow->val == fast->val)
            return true;
        slow = slow->next;
        fast = fast->next->next;

    }
    return false;
}