关于链表的环和逆置的问题：

1.判断单向链表是否有环

快慢指针

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
  public:
	bool hasCycle(ListNode *head)
	{
		ListNode *slow = head;
		ListNode *fast = head;
		while (fast && fast->next)
		{
			slow = slow->next;
			fast = fast->next->next;
			if (slow == fast)
				return true;
		}
		return false;
	}
};

2.判断单向链表是否有环及找环入口

题目描述：

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

题目分析：就是判断并找到一条单链表相交的起始节点，如果没有相交，返回 NULL 即可 。

解题思路：先来看下面的这幅图

给一个快指针，一个慢指针 。假设quick,slow指针在Z点相遇，则slow走了a+b;quick走了a+b+c+b；

因为quick速度是slow的2倍，有

则slow走了a+b;quick走了a+b+c+b；
由时间相同得到(设速度为v) ：
	(a+b)/v = (a+b+c+b)/2v 
	2a+2b   = a+b+c+b 
	       a=c

也就是a=c

这个结论很给力，此时qucik、slow在Z点，而我们现在想到循环入口Y点，头结点到Y点需要a步，而a=c，z再到y是c，所以此时从x,z点走当二者相遇就是Y点了。

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) { 
		if(head == NULL )
			return NULL ;
		ListNode *quick ,*slow;
		quick = head ;
        slow =  head ;
		bool  tag = false ;
		while(quick && quick->next ){ //注意判断条件
			slow = slow->next;
			quick = quick->next->next ; //考虑quick->next 为 NULL 的情况

			if(slow == quick ){
				tag = true ;
				break ;
			}
		}
		if(tag == false )
			return NULL ; 
		for(ListNode *fast = head ; ;){
			if(fast == slow )
				return fast ;
			fast = fast->next  ;
			slow = slow->next ;
		}
    }
};

为了证明是对的 ：

2.单链表的逆置（查看下方链接）

单链表的逆置（C++实现）