本文主要是介绍判断链表是否有环，判断环的入口，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
pre
面试中遇到过，知道解法，但是细节不是很了解，这里重新整理一下思路，通知给出关键部分的理由和证明
问题1：判断链表是否有环
问题分析
首先考虑环出现之后链表的特征，从头开始的链表遍历无法结束，也就是不存在尾节点
这时候第一个想法，一遍遍历链表，直至出现null 或者下一个元素是之前出现过的元素，那么这样时间复杂度为O（n），空间复杂度为O（n）[这里需要缓存之前节点的访问的情况]
下一个问题是这是否能够优化到不需要缓存Node，也就是空间复杂度为O(1)?
这里提出优化算法，声明两个指针，一个指针以步长为1的幅度向后遍历，另外一个指针以步长为2的幅度向后遍历，如果步长为2的指针找到null 或者 与步长为1的指针相撞时，算法结束。算法的时间复杂度为O(N),空间复杂度为O（1）
算法证明
1°如果链表无环，那么快指针必定会访问到null
显得
2°如果链表有环，那么快指针必定会与慢指针相遇
这篇关于判断链表是否有环，判断环的入口的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
