LeetCode---环形链表 II
首先要解决这个题，我们先要明白我们要考虑的情况
如果链表没有环，则直接返回null
ListNode fast=head; ListNode slow=head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; if(fast==slow){ break; } }if(fast==null||fast.next==null){ return null; }如果有环，那我们也要考虑两种情况
圈大
从上面的图片中我们可以看出，当fast一次走两步，slow一次走一步的时候，我们会发现，
slow所走的路程是X+C-Y
fast所走的路程是X+C+C-Y
注意：慢指针不会走了很多圈才会被追上，实际上慢指针最多走半圈
如果实在想不懂，可以看看上面的图，一步一步带入进去
由于fast是一次性走两步，slow是一次性走一步
所以fast所走的路程是slow所走路程的两倍
slow所走的路程是X+C-Y
fast所走的路程是X+C+C-Y
所以我们可以列出等式 X+C+C-Y=2*(X+C-Y)
化简之后就可以看到
X==Y
由于X==Y
所以我们让指针1和指针2同时走，那么它俩就会在入环的第一个节点相遇
圈小
所谓的圈小，就是当slow进环的时候，fast已经走了很多圈了
此时当slow和fast相遇的时候，走的路程分别是
slow：X+C-Y
fast：X+N*C+C-Y
由于fast所走的路程是slow的两倍
所以
2*(X+C-Y)=X+N*C+C-Y
化简后得到
x+c-y=nc
x=(n-1)c+y
当n==0的时候，X==Y，恰好是圈大的情况
当fast走了n-1圈后，依旧是回到相遇点，然后再加上个Y，正好是入环的第一个节点
假设圈的长度是2，当slow走了X的一半的时候，fast恰好入环
此时，slow每走一步，fast就走一圈
完整版代码：
public class Solution { public ListNode detectCycle(ListNode head) { ListNode slow=head; ListNode fast=head; //首先在环中找到相遇的点 while(fast!=null&&fast.next!=null){ slow=slow.next; fast=fast.next.next; if(slow==fast){ break; } } //没找到环的情况 if(fast==null||fast.next==null){ return null; } //定义一个新节点，从头开始走，每次走一步，fast也每次走一步 //当cur和fast相等的时候，跳出循环，此时这个节点就是入环的第一个节点 ListNode cur=head; while(cur!=fast){ cur=cur.next; fast=fast.next; } return cur; } }