本文主要是介绍求单链表是否有环、环长、入环点、链长，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1. 单链表是否有环
用两个快慢指针去判断单链表是否环，快指针的速度是慢指针的两倍，若单链表有环，则两个指针会先后进入环内，并且快指针会从后面追上慢指针。下面来严谨地分析一下两个指针在环内相遇的情况。
假设此时慢指针s和快指针f都在环内，相隔k点，环内共有R点，t时间之后，两指针相遇。
[快指针最终位置 = 慢指针最终位置] -> [(2t mod R) + k = (t mod R)] 假设 2t = aR + x, t = bR + y, a > b -> 2t - aR + k = t - bR -> t = (a - b)R - k
typedef struct node{int value;node *next;
}node_t;int testloop(node_t *head)
{node_t *fast = head;node_t *slow = head;while(fast->next != null && fast->next->next != null) {slow = slow->next;fast = fast->next->next;if(slow == fast) {return -1;//have loop}}return 0;//no loop
}2. 求环长度
t = (a - b)n - k
我们在上面推导出在环内相遇要经过的时间t，那么现在从第一次相遇(k=0)开始算，一直到第二次相遇，慢指针刚好走过一个环长n，即环长等于第一次相遇到第二次相遇，慢指针走的长度。
3. 求入环口
假设第一次相遇点离入环口的距离是x，那么
快指针走的距离：2s = y + nR + x
慢指针走的距离：s = y + x (慢指针在第一次相遇时，不会走到完整的一环)
-> y = nR - x (n不一定是1，环内的指针可能要转几圈才会和环外的指针相遇)
那么我们在第一次相遇时，把慢指针留在原地，把快指针放回起点head处，然后把快指针变为慢指针，两个指针一起以速度1前进，当它们相遇时，相遇点就是入环点4
4. 求链长度
问题2求出环长，问题3求出入环点即y的长度，那么链长只要将它们相加即可。
【Reference】
1.http://www.cnblogs.com/xudong-bupt/p/3667729.html
2.http://www.cnblogs.com/kqingchao/archive/2011/07/06/whether_there_is_a_loop_in_link.html
这篇关于求单链表是否有环、环长、入环点、链长的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
