风乍起
吹皱一池春水
C++，链表快慢指针，leetcode原题。
我们定义快慢两个指针，从第一个结点触发，快指针一次走两个结点，慢指针一次走一个结点，于是会存在如下情况：
- 如果有环，则两个指针一定会再次相遇，且快指针经过的结点数是慢指针的两倍数；
- 如果无环，快指针先碰到空指针。
所以我们假设l_slow为慢指针经过的结点数，l_quick是快指针经过的结点数，环中的结点数为circle，存在如下关系：
l_slow + circle = l_quickl_quick = 2 * l_slow
所以得到关系circle = l_slow，即可求出环的结点数。
那如何找到入环结点呢？
- 先让快指针走
circle步 - 然后慢指针走
- 再次相遇的位置就是环入口结点了。。。
脑海里想象一下那个场景就行了，或者画个图2333。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead) {
if (pHead == nullptr) return nullptr;
ListNode *slow = pHead, *quick = pHead;
if (slow->next) slow = slow->next;
else return nullptr;
if (quick->next) quick = quick->next;
else return nullptr;
if (quick->next) quick = quick->next;
else return nullptr;
int circle = 1;
while (slow != quick) {
if (quick->next) quick = quick->next;
else return nullptr;
if (quick->next) quick = quick->next;
else return nullptr;
slow = slow->next;
circle++;
}
slow = quick = pHead;
while (circle) {
quick = quick->next;
circle--;
}
while (slow != quick) {
slow = slow->next;
quick = quick->next;
}
return slow;
}
};
