环链
环形链表
题目
分析
我们剖析一下代码
bool hasCycle(struct ListNode *head) { struct ListNode* fast = head,*slow = head; while(fast && fast->next) { fast = fast->next->next; slow = slow->next; if(fast == slow) return true; } return false; }
延伸问题：
1.为什么fast和slow会在环中相遇，会不会有这么一种情况呢。就是在环中一直交错永远遇不上？请证明一下。
结论：就上面fast和slow而言是一定相遇的
证明：
第一步：slow和fast，fast肯定是先进环，这时slow是fast入环前距离的一半。
第二步：随着slow进环，fast已经在环里走了一段了，走了 多少和环的大小有关系
第三步：我们这里假设slow进环的时候距离和fast是N
slow每次往前走1步，fast往前走两步，每追一次，判断一下相遇，结果为N-1，也就是说每追一次他们间的距离是一步一步的在减少，直到他们相遇
这里就又衍生出了一个问题就是slow与fast只要是步差为一就可以相遇
2.为什么slow走一步，fast走两步呢？fast可不可以走大于两步呢？
结论：fast走n步，n>2,不一定会相遇
这里分析一个slow走一步，fast走三步的交错与不交错的情况
他们之间的距离变化是每次是两两的减少，这也就意味着可能会交错
上面的奇偶问题也就又衍生出了N是他们的步差倍数就能相遇
环形链表 II
题目
如何求环的入口点
分析
我们先直接放结论一个指针从相遇点开始走，一个指针从链表头开始走，他们会在环的入口点相遇
struct ListNode *detectCycle(struct ListNode *head) { struct ListNode * fast = head,* slow = head; while(fast && fast->next) { fast = fast->next->next; slow = slow->next; if(slow == fast)//相遇 { //相遇节点 struct ListNode * meetNode = fast; while(meetNode != head) { meetNode = meetNode->next; head = head->next; } return meetNode; } } return NULL; }
