I
第一问很简单，就是快慢指针的一种应用。如果链表中存在环，那么快指针必然能够在某个节点上面追上慢指针，于是答案代码如下：
:::C++
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *fast = head, *slow = head;
while (fast != nullptr && slow != nullptr) {
slow = slow->next;
if (fast->next != nullptr) {
fast = fast->next->next;
} else {
break;
}
if (fast == slow) {
return true;
}
}
return false;
}
};
II
第二问要求出链表开始成环的那个节点，从字面意思推测也能猜出这题既然这么出，必然是有某种规律的，因此它实际上就是第一个问题的细化了。假设从头结点到开始成环的第一个节点间长度为x，环的总长度为c，从成环节点到快慢指针相遇节点的距离为m；快指针在相遇的时候绕环A圈，慢指针绕环B圈，由于快指针的速度是慢指针的2倍，因此有关系式：
$$A*c+x+m=2*(B*c+x+m)$$
$$x+m=(A-2B)*c$$
综上我们得出结论，x与m是互补的——当快慢指针在m位置相遇后，再往前走x步即可达到环的起始位置。所以此时问题就转化为，在m位置相遇后，我们如何精确地走出这x步呢？这时我们需要注意到这样一个性质：按照x的定义，如果从起始位置出发，经x步能够走到环的起始位置；而从m位置开始，经同样步数也能够走到相同位置也就是环的起始位置。因此，我们只需要设置两个指针，一个从链表开头走，一个从相遇位置继续走，两者就一定会在环的起始位置相遇。最终代码如下：
:::C++
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *fast = head, *slow = head, *meet = nullptr;
while (fast != nullptr && slow != nullptr) {
slow = slow->next;
if (fast->next != nullptr) {
fast = fast->next->next;
} else {
return nullptr;
}
if (fast == slow) {
meet = fast;
break;
}
}
if (meet == nullptr) {
return nullptr;
}
slow = head; fast = meet;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
};