本文主要是介绍判断单链表是否有环？中点如何判断？入环点如何判断？，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
首先我们需要克服我们一种错误的认知，链表有环，并不是有“死节”，如下所示，左侧的这种链表结构是不存在的，因为在相交的那个节点不可能有两个指针，只有像右侧这种结构才是存在的
判断链表是否有环的方法：
第一种使用哈希表，在遍历的过程中将节点存入哈希表，如果发现某个节点在表中已经存在了，那么这个链表就是有环的，并且这个节点就是入环节点
第二种方法叫做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步的方式来判断链表是否有环。
这篇关于判断单链表是否有环？中点如何判断？入环点如何判断？的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
