给定一个单链表，是否有环是一个常见的而且比较经典的问题。这类问题一般使用快慢指针进行解题。快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2，慢指针每次向前移动1次。在刷题中经常会碰到使用快慢指针来解决问题，这类问题一般都是针对链表进行操作。下面对快慢指针涉及的问题进行一个总结。
问题一：判断单链表是否有环（链表头指针head）
对于这个问题我们可以采用“快慢指针”的方法。就是有两个指针fast和slow。开始的时候两个指针都指向链表头head，然后在每一步操作中：
slow走一步：slow=slow->next;
fast每一步向前两步：fast = fast->next->next
由于fast要比slow移动的快，如果有环，fast一定会先进入环，而slow后进入环。当两个指针都进入环之后，经过一定步的操作之后二者一定能够在环上相遇，并且此时slow还没有绕环一圈，也就是说一定是在slow走完第一圈之前相遇。
参考代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25/**
* 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) {
if (!head || !head->next) return false;
ListNode *fast=head;
ListNode *slow=head;
while(fast->next&&fast->next->next)
{
fast=fast->next->next;
slow=slow->next;
if(slow==fast)
return true;
}
return false;
}
};
问题二：如果存在环，求出环的入口点
假设链表的长为L，起始点到环入口长度为a，环长度为r，则 L = a + r。在快指针进入环到慢指针进入环前的这段时间，若环的长度较短，也许快指针已经走了好几圈了。然后慢指针进入环，设慢指针和快指针在环内相遇时，慢指针在环内走了X步，走的总步数为(包括环内与环外)为S步，显然 S = X + a，那么快指针走了多少步呢？快指针在环内已经走了n圈加X步，即 nr + X 步，其中n最少为1，而走的总步数为 nr + X + a 步。
由于快指针走的总步数是慢指针的2倍，故
由上式得
上式的含义为环入口距离起点的距离(等于a)和相遇点距离环入口的距离(等于r -X)相差整数倍的r。
故让慢指针回到起点，快指针从相遇点开始继续走，步长都为1，则当相遇时，即为环入口。此时慢指针走了a步，而快指针也走了a步
参考代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32/**
* 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 || !head->next) return NULL; //判断是否是空链表或者链表只有一个节点
ListNode *slow=head;
ListNode *fast=head;
while(fast->next&&fast->next->next)
{
slow=slow->next;
fast=fast->next->next;
if(fast==slow)
{
slow=head;//慢指针回到起点
while(fast!=slow)
{
slow=slow->next;
fast=fast->next;//快慢指针每次都只走一步
}
return slow;
}
}
return NULL;
}
};
问题三：如果存在环，求出环的节点个数
如果理解了上面的那个题目，这个题目就比较简单。具体思路：
1）假设经过上面程序找到了入口节点，并将其存入临时变量meetingNode;
2）slow继续按照之前的速度一直往前走，slow=slow->next;
3）一直到slow==meetingNode,此时经过的步数就是环上节点的个数；
由于问题比较简单，这里不给出具体代码实现。
问题四：如果存在环，求出链表长度
其实，到这里，问题已经简单的多了，因为我们在问题1、2、3中已经做得足够的准备工作。我们可以这样求出整个链表的长度：
已经知道起点和入口的位置，两者距离很好求得，环的长度也知道，这题基本上没啥难度。
问题五：两个无环链表是否相交，如果相交，求出第一个公共节点
思路一：
假设有连个链表listA和listB，如果两个链表都无环，并且有交点，那么我们可以让其中一个链表（不妨设是listB）的为节点连接到其头部，这样在listA中就一定会出现一个环。这样问题就转化为问题1和问题2。
思路二：
两个无环链表是否相交，由于链表每个节点只有一个next指针，因此这种情况下的链表拓扑结构形状看起来是一个Y型结构，而不是X型结构。
如果两个链表长度一致，这个很容易，两个指针分别遍历两个链表，每次比较节点是否相等；
如果链表长度不一致，第一步，先求出两个链表的长度，长度差为lendif，然后让指针在长链表先走lendif步，再同时在两个链表上遍历。
参考：
http://www.mamicode.com/info-detail-1450407.html
http://www.mamicode.com/info-detail-1450407.html