寻找链表环的问题算法

寻找链表环的问题一、简介这篇博客主要介绍判断链表是否存在环、寻找环的入口点和计算链表的长度的解决方案，主要是介绍思想，不涉及代码。（因为本萌新的师傅一直教育思想的重要性）
这里主要介绍三种解决方案：
① hash存储
② 反转指针
③ 快慢指针
二、hash存储 1、核心思想
只要将遍历过的节点都存储下来，然后在遍历下一个节点的时候，使用下一个节点来和所存储的节点进行比较，如果存在相等的节点，那么就可以证明该链表存在环
2、判断链表是否存在环
因为这里会频繁的进行查找，因此自然而然的想到使用hash来提高查找效率
步骤如下：

文章图片

首先遍历A节点，将其进行hash运算，运算出的值对哈希表的长度进行取余，假设落在了1，那么就查看这个位置上是否存在元素，若存在就判断是否相等，不存在就将该节点存放在该位置上，依次遍历到F点，应该是如下图

文章图片

此时再遍历F节点的下一节点C节点，C进行哈希运算后取余肯定还是5，因此在它查找到哈希表中下标为5的地方的时候，发现已经有元素存在，则比较两个元素是否相等（问：为什么还要比较是否相等？答：因为首先即使是不同的对象，它们通过哈希运算算出的值可能也会相等；第二，因为我们还会对哈希表的长度进行取余运算，那么即使是不同的哈希值，在取余后得出的值可能也是相等的）。如果哈希表上已经存在相同的节点，那么就可以确认这个链表存在环
3、寻找环的入口点
【寻找链表环的问题】通过 2、判断链表是否存在环已经可以知道，其实在判断到第一个重复节点的时候，该节点就是入口结点
4、计算链表的长度
在遍历链表时，维护一个自增长且初始值为0的Integer对象，在判断到第一个重复节点的时候，该Integer就是此链表的长度
5、小结
时间复杂度O（n）————因为只要遍历完整个链表一次即可（无论是否有环）
空间复杂度O（n）————哈希表会将整个链表存储下来，这个不难理解
① 请问哈希值是怎么算出来的？
这里简单的提一下哈

1 Object类的hashCode.返回对象的内存地址经过处理后的结构，由于每个对象的内存地址都不一样，所以哈希码也不一样。 2 String类的hashCode.根据String类包含的字符串的内容，根据一种特殊算法返回哈希码，只要字符串所在的堆空间相同，返回的哈希码也相同。 3 Integer类，返回的哈希码就是Integer对象里所包含的那个整数的数值，例如Integer i1=new Integer(100),i1.hashCode的值就是100 。由此可见，2个一样大小的Integer对象，返回的哈希码也一样。

②如果哈希表中已存在元素，但是所存在的元素不等于当前元素，那么当前元素应该放在哪？
答：这是经典的哈希碰撞问题，感兴趣的可以自行百度，这里就简单的介绍一种常用的，就是链地址法（也称拉链法）。简单说来就是，如果那个位置上有元素，那就以将那个元素的尾节点设为当前元素，这样就是以数组+链表的形式来存储我们的元素，像我们常用的HashMap就是这样来解决哈希碰撞的问题
该算法最大的优点：① 理解容易（个人的感觉）
② 由于使用了hash提高了查找速度，因此时间复杂度还是比较低的
缺点：如果链表比较大，那么就需要很大的存储空间
那么有没有不需要存储空间的方案呢？当然有，请耐心的跟随我来看看下面的这两种方案
三、反转指针 1、核心思想
将每一个遍历的节点指向上一次遍历的节点，如果能够回到头节点则链表存在环，否则不存在环（蛤意思？博主第一次看到这句话的时候也是懵X的状态，那么就请看下面的图方便大家理解）
2、判断链表是否存在环
以下图为例

文章图片

首先A为头节点，在获取A节点的下一节点B节点之后，将A的下一节点指向Null。如图

文章图片

然后继续，在获取B节点的下一节点C节点之后，将B的下一节点指向A。如图

文章图片

按照这种规则遍历到E节点，在获取E节点的下一节点C节点之后，将E的下一节点指向D。如图

文章图片

这里是重点
这里是重点
这里是重点
这个时候因为反转的原因，C节点的下一节点只指向B。那么继续遍历和反转，如图

文章图片

再遍历和反转，如图

文章图片

这样就遍历回头节点了，仔细想想，如果一个链表不存在环的话，它会回到头节点吗？答案肯定是否定的，没有环的链表只会单纯的被反转，然后尾节点变头节点而已
再来观察反转后的有环链表

文章图片

是不是发现环的顺序被反转了？挺有意思的对吧。那么应该怎么还原呢？
相信聪明的小伙伴已经能想到了，再遍历一次即可（让我想起没有什么是一颗猴赛雷搞不定的。如果有，那就两颗）
3、寻找环的入口点
这种方式寻找入口结点就没那么容易了，如果一定要用这种方式来查找的话，博主只能用一种比较生硬的方式来寻找
那就是在最开始的时候克隆链表，只反转链表的副本。如果存在环，则同时遍历链表和链表副本，遍历的时候一直比较两个链表的下一节点是否相等，只要不相等，则可说明当前节点是入口结点
（问：为什么这样可以找到入口结点？答：因为仔细在反转链表的时候我们就知道，如果链表存在环的话，那么链表的环是会被反转的。因此这个时候遍历原链表和链表副本（环被反转的原链表）时，在到达入口结点时，原链表的入口节点指向的是原来环的第二个结点，而链表副本（环被反转的原链表）的入口节点指向的是原来环的最后一个节点（因为被环被反转了））
4、计算链表的长度
既然找到入口节点，那么求得链表的长度也不是什么难事。只要比较原链表和链表副本的时候，在原链表中加入一个自增的Integer，并且在判断到入口节点的时候，原链表再遍历一次环即可，该Integer就是链表的长度。
那么能不能不用去再遍历一次环呢？
这个当然可以，用数学公式证明一下即可：
设起点到入口节点的距离为a，环的长度为b
那么链表的长度L=a+b
再反转链表的时候携带一个自增且初始值为0的Integer对象，那么在遍历回头节点的时候，该Integer的值应该为2a+b
在找入口节点的时候携带一个自增且初始值为0的Integer对象，那么在找到入口节点时，该Integer的值应该是a
那么下一步应该怎么做就不用我说了吧？
扣666啊（博主有点神经质，别介意哈）
咳，回到正题，接下来用第一个Integer减去第二个Integer即
L=2a+b - a
得到链表的长度
5、小结
时间复杂度O（n）————因为只要遍历完整个链表两次即可（无论是否有环）
空间复杂度O（1）/O（n）————如果只是判断是否有环的话，不需要备份链表。但要是想寻找入口节点和求链表长度的话，就需要备份链表，故空间复杂度为O（n）
该算法最大的优点：① 判断链表是否有环不需要额外的空间
② 相比第一种方法，省去了一些繁琐的操作（如进行哈希运算、取余、查找哈希表并且判断是否相等等）
缺点：
① 不容易理解为什么反转之后能回到头节点（比如博主之前就一直纠结这个问题）
② 如果是寻找入口节点和求链表长度的话，那么需要额外空间的问题还是没有解决
那么还有没有其他更好的方式？
其实是最后一种方案驱动着博主写这篇博客，前两种就起个抛砖引玉的作用
四、快慢指针 1、核心思想
在链表中放一快一慢指针（只要存在环，快慢指针就会相遇）
2、判断链表是否存在环
在链表的头节点放置快指针（每次前进两个节点），一个慢指针（每次前进一个节点），只要两个节点相遇则该链表存在环；否则就是快指针遍历到尾节点，说明该链表不存在环
3、寻找环的入口点
快慢指针相比之前两种来说理解起来比较困难，这里就尽量多用公式来证明。如图

文章图片

在起始点A放置一个快指针，步长为2（每次前进两个节点）；一个慢指针，步长为1（每次前进一个节点）。B点为环的入口点，C点为两指针碰撞点（碰撞时慢指针肯定还在走第一圈）
假设链表长度为L，在C点碰撞时，慢指针走了S步，那么快指针就走了2S步
此时 ① 对慢指针进行分析 S = AB+BC
② 对快指针进行分析2S = AB+BC+nR（R是环的长度R=BC+CB，n是圈数）
用② - ① ，得 S = nR
结合① 可知 AB+BC = nR
那么 AB+BC = （n-1）R+R = （n-1）R + L - AB
AB = （n-1）R+（L- AB -BC ）= （n-1）R +CB
由此可知，起始点到入口点的距离AB就相当于相遇点到入口点加上（n-1）圈
因此，我们如果在A点和C点都放一个步长为1的指针，那它们的相遇点就是入口节点
4、计算链表的长度
① 记录环长：
在C点碰撞时候，快指针和慢指针再接着走。下次相遇时快指针刚好比慢指针多走了一圈，也就是快指针多走得步数为环的长度
② 记录起始点到环的入口节点的距离AB：
由于之前已经找到了环的入口节点，因此在头节点放一个慢指针遍历到入口节点即可得到AB的长度
将环长和AB相加即可得到链表的长度
5、小结
时间复杂度O（n）————因为只要遍历完整个链表一次即可（无论是否有环）
空间复杂度O（1）————不需要额外空间
问题1：为什么链表有环快慢指针一定会相遇？
答：慢指针到达入口节点时，不管快指针在环的哪个地方
只要慢指针走到环的一半时候，由于快指针的步长是慢指针的两倍，快指针一定走了一圈。
那只要慢指针在环里，它们怎么可能不会相遇？如果还不能够理解的建议自己画图感受一下
问题2：为什么第一次相遇的时候慢指针一定没有走完一圈？
参考下图：观察最极限的情况

文章图片

接着遍历，如图

文章图片

然而还是被追上了（要是追妹子有这么好追就好了）

文章图片

该算法最大的优点：① 判断链表是否有环不需要额外的空间
② 不影响链表原有结构（相比反转指针）
缺点：
① 不容易理解，可能会很纠结
拓展：求单向链表倒数第三个节点
一般情况下是不是需要遍历两次？
第一次求链表的长L
第二次遍历到L-2
那能否遍历一次就得到呢？
答案当然是可以的，在起始点放置两个慢指针，步长都为1（每次遍历一个节点），
让慢指针A先走两步，慢指针B再开始走，这样AB指针差距是两个步长。那么当指针A到达链表尾节点的时候，指针B就在链表的倒数第三个节点
五、总结以上就是想和大家分享的三种方案，如果有不对的地方请拍砖，或者有其他更好的解法也欢迎分享~