1分钟交你判断单链表是否有环问题

小呆是某某计算机专业的学生。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 排版