力扣 142 环形链表

判断一个链表有无环，并且如果有环指出入环的位置。

1、判断有无环是通过 一快一慢指针来判断的。快的指针走每次走两步、慢的指针每次走一步，这样如果没有环的话他俩不会相遇。如果有环则一定相遇。

为什么一定相遇呢？ 因为快指针走两步、慢指针走一步，快指针每次比慢指针多走一步，所以快指针必定能和慢指针相遇。

2、入环的位置：设开始距离入环位置为x ,入环位置到相遇的位置为y（顺时针），相遇位置距离入环位置（顺时针）为z。

根据快慢指针速度关系可得路程关系：  2*(x+y)=x+n(y+z)   解得x=(n-1)*(y+z)+y   ，即x与y相同。

为什么慢指针走的路程是 x+y 呢，为什么慢指针没有转圈呢？

注意慢指针入环的时候，快指针一定入环了。此时快指针和慢指针相遇的时候，慢指针肯定没走完一圈。如果慢指针走完一圈、快指针就走完两圈了，他们一定会在中途遇见的。把圆圈拉直就好理解了，当慢的走完一圈，快的走完两圈，肯定会相遇。（不懂就看卡尔的讲解）

为什么解出来是x=y呢 因为剩下的（n-1）*（y+z）是在那里转圈。结论就是当相遇的时候，相遇节点到入环的地方等于头节点到入环的距离。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
      ListNode *slow=head,*quick=head;
      if(slow==NULL)
      return NULL;
      int max=10000;
      while(1){
          if(max==0)
          break;
          max--;
          if(slow->next==NULL)
          return NULL;
          if(quick->next==NULL||quick->next->next==NULL)
          return NULL;
          slow=slow->next;
          quick=quick->next->next;
          if(slow==quick)
          break;
      }
      if(max==0)
      return NULL;
      ListNode *p=head;
      while(p!=slow){
          p=p->next;
          slow=slow->next;
      }
      return slow;
    }
};