把环形链表讲清楚！| LeetCode:142.环形链表II (opens new window)

这道题有两问，
一个是链表有没有环，一个是环的入口是哪个。
判断链表有没有环，应该考虑用双指针，一个快指针一个慢指针，如果有环则快慢指针一定会相遇，如果无环则不会相遇。
注意，快指针一次走2个节点，慢指针一次走1个节点，这样快指针永远比慢指针多走1个节点，在环里就一定会与慢指针相遇。如果你设成快指针一次3个节点，慢指针一次1个节点，那快指针有可能因为一下子跨过慢指针从而导致没有与慢指针相遇。

①慢指针在走完环的第一圈之前，一定已经与快指针相遇了，假设左边为快指针，右为慢指针，一节为一圈，如图慢指针走过一圈时，快指针已在慢指针前面，说明在慢指针走完一圈之前，快指针就已经在某刻超过慢指针即相遇，即此时慢指针还没走完一圈就相遇。

快慢指针相遇只是为了找出index1
利用下图数学推理可知x=z，所以把快慢指针相遇的地方定义为index1，头结点定义为index2，然后index1与index2一起走每次走一步，到环的入口处就相遇(因为x=z嘛你们俩又都是每次一起走一步)

 //注意只需要判断fast和fast的next不为空即可，不用限定fast->next->next也不为空。因为1-2-null可以，而null或者1-null(快指针都走不了第一步咋判断)只能返回null
fast为空你还往后走那就是对空指针进行操作是出错的，fast的next为空例1-null，那你fast走next再走next，那就是1走向next即到null，还next即对null操作，那就是对空指针进行操作即错，fast的next的next就可以为空例1-2-null，那快指针就从1跳到null，没问题，指针可以指向null啊，可是你要是继续在null的位置上继续往后即操作null让其->next即对空指针进行操作就错所以不进入循环了。

大致代码套路

fast=head;
slow=head;
while(fast!=null&&fast->next!=null){ 
   fast=fast->next->next;
   slow=slow->next;
   if(fast==slow){
        index1=fast;
        index2=head;
        while(index1!=index2){
                   index1=index1->next;
                   index2=index2->next;
              }
          return index1;
     }
}
return null;