小呆是某某计算机专业的学生。linglingling，伴随这铃声，同学们都准时来上课了。
老师：这节课是计算机课，我们学习了单链表，请同学说一下什么是单链表。
同学们纷纷举起了手。好，小白你来说。
小白：单链表是一种线性表，它的存储单元可以不是连续的，从头节点开始，每个节点都有一个指针，指向下一个节点，最后一个节点指向 null,头节点不被指向。
老师：好，那么谁来说一下链表的这种结构有什么优点呢？
同学们纷纷举起了手。好，小黄你来说。
小黄：线性表的一种，链式表的在存储空间中可以是不连续的，因此存储密度较低，还有增删的时候只需要改变指针的指向就可以了，而不是像顺序表那样，比如你要在某个位置添加一个元素，那么其他的元素都要向后移，因此链式表增删相对较快些。
老师：好，大家掌握的不错啊，那么大家思考一个问题，怎么判断一个单链表是否有环。
如图，这样的单链表就是有环的链表。
注：数字 1-10 代表节点 1-10,节点存储值和指针。
老师：好，小红同学你来说。
小红：两层循环，第一层循环从头遍历，第二层循环从头遍历到第一层循环当前的节点，如果存在相同的节点，那么链表有环。
老师：好，这样做确实是可以判断是否有环，但是效率并不高，遍历两次时间复杂度 o(n^2),由于没有开辟额外的空间，所以空间复杂度 o(1)。哪位同学还有更好的方法吗。
老师：好，小明你来说一下。
小明：一层循环，创建一个 hashset,把节点放到 hashset 中，如果出现相同的节点，说明单链表有环。
老师：好，小明同学采用了空间换时间的方法，此时的时间复杂度 o(n),由于开辟了和链表单独相关的 n 的空间，所以空间复杂度 o(n)。那还有没有更好的方法呢。
老师：谁是计算机课带表啊。
课带表：这里。
老师：那么你来说说，有什么更好的方法。
课代表：
如果两个人在环形的跑道上赛跑，快的人总会再次追上慢的。
因此我们可以假设用两个指针比如两个赛跑的同学，一个快指针，一个慢指针，我们称为快慢指针方法。
那么我们来说一下说它是实现思路：
快指针每次移动两步，慢指针每次移动一步，如果两个节点相等，则说明有环，返回 true,否则返回 false。
代码实现大概是是这个样子的。
Node fast = head; Node slow = head; while(fast.next != null) { fast = fast.next.next; slow = slow.next; if (slow == fast) return true; } return false;老师：非常好，这个方法的时间复杂度为 o(n),空间复杂度为 o(1)。请大家回去思考一个问题，如何判断单链表是否有交点。下节课老师提问，同学们下课。这是我两年前的一个文章，希望对大家有帮助，后面小咖会继续写原创文。感谢大家的观看，如果对你有帮助，求个三连。
本文使用 mdnice 排版
