LeetCode#141

LeetCode#141环形链表

题目链接
一道链表问题，通俗来说就是判断一个链表中是否有环力扣的翻译真绝了，除了开辟额外，如使用哈希表等等，还有其他的方式吗？那为了不开辟额外的空间，我们需要引入一个新的指针方式：快慢指针。
顾名思义，快慢指针就是两个指针，一个跑的快，一个跑得慢，它是在链表中检测是否有环的一个重要方式，具体实现方式是：声明两个指针，接下来进行循环，快指针每次步进两下，慢指针每次步进一下，如果遇到空指针那么肯定是找到了链表结尾，没有环，而如果快指针最终追上了慢指针（两个指针相遇），那么就一定是在链表中存在环。具体原理可以使用严谨的数学公式进行推导…而使用的话，我们只需要类比在操场跑圈即可：如果都围着操场跑步，那么跑得快的同学总会有追上跑的慢的同学的时候（扣圈），但是如果在直道上，跑步速度不同的两个同学是永远不会相遇的。
附代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == nullptr || head -> next == nullptr)
            return false;
        ListNode* fast = head -> next;//快指针
        ListNode* slow = head;//慢指针
        while(fast != slow)
        {
            if(fast -> next == nullptr || fast -> next -> next == nullptr || slow -> next == nullptr)
                return false;
            fast = fast -> next -> next;
            slow = slow -> next;
        }
        return true;
    }
};