【Java数据结构】判断单链表是否有环，并且找出环的入口

太过爱你忘了你带给我的痛 2023-02-26 01:05 27阅读 0赞

一：判断是否有环  
思路：使用快慢引用法解决 是否有环  
假设链表是一个有环链表，且由f指向c构成环。那么 使用两个指针 A 和 B，让两指针同时向后遍历 而且B的遍历速度是A的两倍，呢么如果是有环的话，B终究会追上A。因此我们可以 以AB是否相遇作为判断是否有环的必要条件。

下面是图例：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDg3OTc0Mw_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDg3OTc0Mw_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDg3OTc0Mw_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDg3OTc0Mw_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDg3OTc0Mw_size_16_color_FFFFFF_t_70 4][]

最终BA在e相遇，于是可以得出 此链表有环。

代码：

public Entry<E> isLoop(){
            Entry<E> fast = first , slow = first;//定义两个指针，分别是快和慢
            //遍历一遍链表，如果最后是null的话就代表没有环
            while (fast != null && fast.next != null){
                fast = fast.next.next;
                slow = slow.next;
                //如果俩相遇了，代表有环
                if (fast == slow){
                    return fast;
                }
            }
            return null;
        }

二：求出成环的位置  
思路：s=vt（路程=速度\*时间）用方程思想列等式解  
因为路程知道，速度知道（二倍关系），时间也知道（相等），所以可以列等式求关系。再用代码体现出关系，就可以解决这道题了。

如图：假设链表是Link fast是快的那个指针，Slow是慢的呢个指针，蓝色是fast走过的路程，绿色是slow走过的路程

K是环的入口，P是快慢指针相遇的地方

a，b，c 分别代表三段长度。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDg3OTc0Mw_size_16_color_FFFFFF_t_70 5][]

所以图就可以变成：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDg3OTc0Mw_size_16_color_FFFFFF_t_70 6][]

然后，让指针从 相遇点p 和起始点 同时遍历，这样由于 c = a 所以p和first在k相遇，而k就是入口点。

public Entry<E> getIntersectEntry(){
            Entry<E> meet = isLoop();
            if(meet == null){
                return null;
            }
            Entry<E> p = meet;
            Entry<E> q = first;
            while (p!=q){
                p = p.next;
                q = q.next;
            }
            return p;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDg3OTc0Mw_size_16_color_FFFFFF_t_70]: /images/20230209/0dc6b46740a345269b518abb8a15f638.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDg3OTc0Mw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190529173620536.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDg3OTc0Mw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDg3OTc0Mw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190529173658788.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDg3OTc0Mw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDg3OTc0Mw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20190529173729229.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDg3OTc0Mw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDg3OTc0Mw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20190529173749506.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDg3OTc0Mw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDg3OTc0Mw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20190529175933519.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDg3OTc0Mw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDg3OTc0Mw_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20190529203326403.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDg3OTc0Mw==,size_16,color_FFFFFF,t_70