|
一、简述floyd环检测算法：（我将其分为2部分）
1.检测是否有环：2指针龟和兔，兔的速度是龟的2倍，同时出发，两者将相遇与环中某点。代码如下：
ListNode* slow = head;
ListNode* fast = head->next;
//这里起点不同
while (slow != fast)
{
if (!fast || !fast->next)
return false;
slow = slow->next;
fast = fast->next->next;
}
return true;
2.找环的入口：将其中一指针置回起点，另一指针在之前相遇之处不动。此时同时以相同速度向前进，两者将相遇与环的入口。代码如下：
fast = fast->next;//
slow = head;
while (slow != fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
二、在做LeetCode?142. 环形链表 II这道题时，发现自己写的和题解不一样嗷。觉得很奇怪。
题解：（来源：https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/）
fast = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
- 为什么它可以作一个动作（即置回原点）即可，我需要再让fast指针再往前走一步才能得到正确的答案呢？
一行行比对才发现异同点：题解作者的fast和slow是在同一起点head出发的，而我写的slow指针在head，fast指针在head头结点的下一个结点。因此第一部分代码也有所不同，即以while(1)为循环条件，遇到slow == fast再break出来。
- 那如果在检测是否有环部分，两指针起点不一样，应该怎样理解和确定第二部分（即找环入口部分）的两个指针的起点呢？
?其实slow在head、fast在head的下一个结点这种赋值方法，可以看成是：两指针原在头结点的前一个结点同时出发，只是各自先走了一步。这样就和题解做法相同了。
而第二部分代码中，“将其中一个指针置回起点”中的起点，指的应该是第一部分中两个指针以相同地方开始的起点。若第一部分代码中两指针起点不同，第二部分代码slow重新置为head，（为方便叙述，将头结点的前一个结点称为pre）由于slow在head即pre->next，slow已经前进了一步，为保持同步以便得到正确答案，fast也应该前进一步，故有fast = fast -> next这一动作。若slow以pre为起点，fast可以不动。（但pre其实并不存在）
这样也就可以解释这道题287. 寻找重复数为什么在第二部分以动作slow = 0为开头。
第一部分fast =?nums[nums[0]]，slow?=?nums[0]，即以数组第一个元素的前一个元素为起点（实际并不存在这个元素）。由于题目条件已限定数组中所有元素值的范围为[1,n-1]，0不会是任一元素，函数以值为映射，故起点为slow = 0。
若有误，欢迎交流与指正。
（我滴小小心得！每天进步一点点妈妈夸我小天才~）
|