快慢指针判断链表是否有环

关于链表是否有环，其实是一系列问题，主要包括以下几个：

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

使用快慢指针fast和slow，fast每次走两步，slow每次走一步，如果有环，肯定会相遇，如果没有，则指针fast遇到NULL退出。追及相遇问题。

第一种方法，

将所有的遍历过的节点用某个结构存储起来，然后每遍历一个节点，都在这个结构中查找是否遍历过，如果找到有重复，则说明该链表存在循环；如果直到遍历结束，则说明链表不存在循环。

这个结构我们可以使用hash来做，hash中存储的值为节点的内存地址，这样查找的操作所需时间为O(1)，遍历操作需要O(n)，hash表的存储空间需要额外的O(n)。所以整个算法的时间复杂度为O(n)，空间复杂度为O(n)。

第二种方法

比较的特别，是使用反转指针的方法，每过一个节点就把该节点的指针反向。

当有环的时候，最后指针会定位到链表的头部，如果到最后，都没有再到头部，那说明链表不存在循环。

这个方法会破坏掉链表，所以如果要求是不能破坏链表的话，我们最后就还需要反转一下，再将链表恢复。

这个方法使用的空间复杂度为O(1)，其实是使用了3个指针，用于进行反转。同时，时间复杂度为O(n)。

第三种方法，

可能大家已经知道了，同时也是面试官大多想要得到的答案，就是快慢指针。

快指针pf(f就是fast的缩写)每次移动2个节点，慢指针ps(s为slow的缩写)每次移动1个节点，如果快指针能够追上慢指针，那就说明其中有一个环，否则不存在环。

这个方法的时间复杂度为O(n)，空间复杂度为O(1)，实际使用两个指针。

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.如果快指针每次走三步，四步，五步…会怎么样？

　　不管快指针走多少步，只要有环就会与慢指针相遇，因为慢指针每次都走一步。但是如果快指针每次走三步以上，就会导致上述公式不成立。比如说快指针每次走三步，则公式变为：

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

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

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

举例：头结点之后就是环的入口，环除了入口还有一个节点，fast每次走三步，slow每次走一步，第一次会在环的入口相遇，分别从第一次碰撞点Pos、头指针head开始走，无法相遇。