大家好，又见面了，我是全栈君。
找含单链表的环入口点
问题1：怎样推断单链表中是否存在环（即下图中从结点E到结点R组成的环）？
分析：设一快一慢两个指针（Node *fast, *low）同一时候从链表起点開始遍历，当中快指针每次移动长度为2。慢指针则为1。则若无环，開始遍历之后fast不可能与low重合，且fast或fast->next终于必定到达NULL；若有环。则fast必定不迟于low先进入环，且因为fast移动步长为2，low移动步长为1，则在low进入环后继续绕环遍历一周之前fast必定能与low重合（且必定是第一次重合）。于是函数可写例如以下：
bool hasCircle(Node* head, Node* &encounter)
{
Node *fast = head, *slow = head;
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
{
encounter = fast;
return true;
}
}
encounter = NULL;
return false;
}
问题2：若存在环，怎样找到环的入口点（即上图中的结点E）？
解答：如图中所看到的。设链起点到环入口点间的距离为x，环入口点到问题1中fast与low重合点的距离为y。又设在fast与low重合时fast已绕环n周（n>0），且此时low移动总长度为s，则fast移动总长度为2s。环的长度为r。则
s + nr = 2s,n>0 ①
s = x + y ②
由①式得 s = nr
代入②式得
nr = x + y
x = nr – y ③
现让一指针p1从链表起点处開始遍历，指针p2从encounter处開始遍历，且p1和p2移动步长均为1。则当p1移动x步即到达环的入口点，由③式可知，此时p2也已移动x步即nr – y步。
因为p2是从encounter处開始移动。故p2移动nr步是移回到了encounter处，再退y步则是到了环的入口点。也即，当p1移动x步第一次到达环的入口点时。p2也恰好到达了该入口点。于是函数可写例如以下：
Node* findEntry(Node* head, Node* encounter)
{
Node *p1 = head, *p2 = encounter;
while(p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
原文来自:http://blog.csdn.net/wuzhekai1985/article/details/6725263
有错误欢迎提出， 分享请标明出处， 谢谢！
感觉好的话就顶一个。 感觉不错的话就踩一个。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116061.html原文链接：https://javaforall.net
