判断单链表里面有没有环系列

1.判断单链表是否有环

使用两个slow, fast指针从头开始扫描链表。指针slow 每次走1步，指针fast每次走2步。如果存在环，则指针slow、fast会相遇；如果不存在环，指针fast遇到NULL退出。

2.求有环单链表的环长

在环上相遇后，记录第一次相遇点为Pos，之后指针slow继续每次走1步，fast每次走2步。在下次相遇的时候fast比slow正好又多走了一圈，也就是多走的距离等于环长。

设从第一次相遇到第二次相遇，设slow走了len步，则fast走了2*len步，相遇时多走了一圈：
环长=2*len-len。

3.求有环单链表的环连接点位置

第一次碰撞点Pos到连接点Join的距离 = 头指针到连接点Join的距离，因此，分别从第一次碰撞点Pos、头指针head开始走，相遇的那个点就是连接点。

在环上相遇后，记录第一次相遇点为Pos，连接点为Join，假设头结点到连接点的长度为LenA，连接点到第一次相遇点的长度为x，环长为R。

第一次相遇时，slow走的长度 S = LenA + x;

第一次相遇时，fast走的长度 2S = LenA + n*R + x;

所以可以知道，LenA + x = n*R;　　LenA = n*R -x 　

4.求有环单链表的链表长

2中求出了环长，3中求出了连接点的位置，相加就是链表长。

5.如何判断两个链表（不带环）是否相交

将其中的一个链表首尾相连，然后判断另一个链表是否带环即可。