判断单链表是否有环？中点如何判断？入环点如何判断？

首先我们需要克服我们一种错误的认知，链表有环，并不是有“死节”，如下所示，左侧的这种链表结构是不存在的，因为在相交的那个节点不可能有两个指针，只有像右侧这种结构才是存在的

判断链表是否有环的方法：

第一种使用哈希表，在遍历的过程中将节点存入哈希表，如果发现某个节点在表中已经存在了，那么这个链表就是有环的，并且这个节点就是入环节点

第二种方法叫做Floyd判圈算法，或者是龟兔赛跑算法，其实就是快慢指针思想，算法流程如下所示：

使slow和fast这两个指针都指向链表的头部，slow指针每次走一步，fast指针每次走两步

由于fast指针走得快，如果链表有环，那么在移动的过程中，fast指针一定能在后面超越slow指针。如下所示：

如果链表有环，这两个指针一定能在某次移动之后相遇。如下所示：

我们可对该方法进行验证：

状态1：

如果在超越之前，fast落后slow一步，那么在下次移动的时候，fast走两步，slow走一步，两个指针就此相遇，如下所示：

状态2：

如果在超越之前，fast落后slow两步，那么在下次移动之后，fast走两步，slow走一步，又变成了状态1

以此类推，fast落后三步的时候，fast走两步，slow走一步，又可以变成状态2

因此我们可以得出如果链表有环，那么快慢指针就一定能够在某次移动后相遇

寻找链表的中点：

我们可以设置两个指针，快指针每次走两步，慢指针每次走一步，快指针走完整条链表时，慢指针指向的节点就是链表的中点

寻找链表的倒数第K个节点：

设置p1和p2两个指针，让p2指针先走K-1步

然后两个指针每次都走一步，p2指针走完链表后，p1指针指向的节点就是倒数第k个节点

寻找链表的入环点：

如下所示设置两个指针slow和fast，

快指针每次走两步，慢指针每次走一步

如果快慢指针能相遇，那么说明链表有环

快慢指针相遇之后，让快指针重新回到头节点，然后让快慢指针每次都只走一步，两个指针肯定能在某次移动之后再次相遇，这个相遇的节点，就是环形链表的入环点

fast指针每次移动3步是否可行？4步？5步？

是可行的，但可能会导致遍历的步数较多，并且可能会导致快指针直接跳过慢指针，无法检测到环。所以，一般情况下，推荐使用快指针每次移动2步，慢指针每次移动1步的方式来判断链表是否有环。