快慢指针思想O(n)

时间复杂度计算：

假设起点到环入口长度为x，环的长度为n-x，那么s慢指针和快指针距离假设最坏情况来讲为n-x

当s慢指针走到入口也就是x步，那么快指针f就是2x步,也就是x+2x

然后s和f的距离是n-x步，每迭代一次快指针会追一步，所以说迭代n-x步之后，它就会追上慢指针s，然后这里就一共是3(n-x)

最后x + 2x + 3(n - x) = 3n 所以时间复杂度为：O(n)

/**
 * 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 || !head->next) return false;  // 如果空或者只有一个点那就直接返回false
        auto s = head, f = head->next;  // s慢指针，f快指针
        while(f) {  // 快指针不空继续走
            s = s->next, f = f->next;  // 慢指针s向后走一步，快指针再向后走一步也就是比满指针多走一步
            if (!f) return false;  // 如果快指针空结点了说明没有环直接false
            f = f->next;  // 否则快指针向后一步
            if (s == f) return true;  // 如果快指针和满指针相同（相遇）了就说明是一个环返回true
        }
        return false;
    }
};