题解 | #判断链表中是否有环#

/*
描述
判断给定的链表中是否有环。如果有环则返回true，否则返回false。
Restrict:
使用空间复杂度为1的方法
输入:
分为2部分，第一部分为链表，第二部分代表是否有环，然后回组成head头结点传入到函数里面。-1代表无环，其他的数字代表有环，这些参数解释仅仅是为了方便读者自测调试

示例1
输入：
{3,2,0,-4},1
返回值：
true
说明：
第一部分{3,2,0,-4}代表一个链表，第二部分的1表示，-4到位置1，即-4->2存在一个链接，组成传入的head为一个带环的链表 ,返回true

Main idea:
快慢指针法，若存在环，则快指针（一次走两步）每次行走会接近慢指针（一次走一步）一步，因此若存在环则快指针一定会赶上慢指针（链表长度有限）
*/

class Solution {
public:
    bool hasCycle(ListNode* head) {
        if (head == nullptr)
            return false;
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast)
                return true;
        }
        return false;
    }
};