class Solution {public:ListNode* detectCycle(ListNode* head) {ListNode* dummyHead = new ListNode(0,head);ListNode* cur = head;int now = 0,last = 0;   // now记录从虚拟头节点到当前结点的距离，last保存上一个now的值while(cur!=nullptr){ListNode* tmp = dummyHead;now = 0;while(tmp!=cur){tmp = tmp->next;now++;}// 核心语句：当last值小于等于now值说明cur是环的起点if(now <= last){return cur;}last = now; // last保存上一个now值cur = cur->next;}return nullptr;}
};

• 时间复杂度：O(n^2)。这段代码的核心是两个嵌套的 while 循环，外层循环遍历链表中的每个节点，内层循环遍历链表中从虚拟头节点到当前节点的距离。因此，总的时间复杂度为 O(n^2)。
• 空间复杂度：O(1)。这段代码只使用了常数级别的额外空间，即定义了几个指针和两个整型变量，因此空间复杂度为 O(1)。

但这种解法的时间复杂度为 O(n^2)，并非最优解，如果用哈希表来判断是否出现重复也只需要 O(n)。但由于只是想记录下自己的解法，所以也写出来了，算是拓展途径。由于代码随想录中的哈希表在后面章节，并且此题哈希表也不是最优解，因此这里就不放哈希表的解法了。

双指针

1.怎么确定是否有环？

使用两个指针 fast 和 slow，fast 指针每次走两步，slow 指针每次走一步。如果有环，那么它们一定会在环内某处相遇。

原因：如果有环，那么两个指针一定最后是在环内一直转圈，而由于 fast 指针每次都比慢指针多走一步。可以理解成快指针每次都和慢指针的距离缩小1步，那么他们之间的距离最终一定会缩减为0即相遇。

2.确定有环后怎么确定环的入口？

这里就要用到数学推导了。如下图，a 为头结点到环入口的距离，b 为环入口到相遇点(紫色)的距离，c 为相遇点到环入口的距离。那么 fast 指针走的距离 S_f = a+n(b+c)+b，而 slow 指针走的距离为 S_s=a+b，那么就有

也就是从头节点到环入口的距离刚好等于 n-1圈的环加上 c 的距离，也就是说当快慢指针相遇时，我们可以再定义一个指针起始点为头节点，每次和 slow 指针一样也是走一步，那么根据上面的式子他们一定会在环的入口相遇。

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast = head;ListNode* slow = head;// 链表为空或者只有一个节点且无环时直接返回nullptrwhile(fast != nullptr && fast->next != nullptr) {// 慢指针走一步，快指针走两步slow = slow->next;fast = fast->next->next;// 快慢指针相遇，此时从head和相遇点，同时移动直至相遇if (slow == fast) {ListNode* ptr = head;while (ptr != slow) {ptr = ptr->next;slow = slow->next;}return ptr; // 返回环的入口}}return nullptr;}
};

• 时间复杂度：O(n)。其中 n 为链表中节点的数目。在最初判断快慢指针是否相遇时，slow 指针走过的距离不会超过链表的总长度；随后寻找入环点时，走过的距离也不会超过链表的总长度。因此，总的执行时间为 O(n)+O(n)=O(n)。
• 空间复杂度：O(1)。我们只使用了 slow，last 和 ptr 三个指针。