环形链表

题目链接：142、环形链表Ⅱ
题目描述：给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

思考

本题不仅考查对链表的操作，而且还需要一些数学运算
判断链表是否有环
如果有环，这么找到这个环的入口

那么怎么判断链表是否有环呢？

使用快慢指针法，都从头节点出发
快指针走两步（很重要），慢指针走一步
如果在走的过程中，快慢指针相遇，则证明有环
（可看成slow不动，fast快指针一步一步追赶slow）
如动图所示：

如果有环，如何找到这个环的入口

假设从头结点到环形入口节点的节点数为x。环形入口节点到 fast指针与slow指针相遇节点节点数为y。从相遇节点再到环形入口节点节点数为 z。如图所示：

接下来用数学思想来解题：
满指针slow走了有x+y，快指针fast走了x+n*（y+z），因为快指针可能不止走了一圈而是走了好多圈为了等慢指针。

因为fast指针是一步走两个节点，slow指针一步走一个节点，所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：
(x + y) * 2 = x + y + n (y + z)；
x + y = n (y + z)；
x = n (y + z) - y；
x = (n - 1) (y + z) + z；（n一定>=1）

代码如下

//环形链表。如何判断环形链表？怎么找到入口？疑难点？
 class Solution {
public:
    ListNode *detectCycle(ListNode *head){
	fast = head;
	slow = head;
	while(fast != null && fast->next!=null){
		//fast快指针是两步一跳，而慢指针走一步，不用判断慢为null
		fast = fast->next->next;
		slow = solw->next; 
		if( fast == slow){
			//fast与slow相遇，说明找到了环
			index1 = fast;
			index2 = head;//index1是相遇的点。index2是从头部出发 
			while(index1 != index2){
				index1 = index1->next;//
				index2 = index2->next;//直到index1和2再次相遇终止循环 
			} 
		return index1;//返回环的入口	
		}
		 
	}
	return null;	
	}
	}