如何判断单向链表是否带环，有回环问题。

左手的ㄟ右手 2021-10-18 07:16 498阅读 0赞

问题描述：

一个单向链表的结构，其中一个节点通常为保存一个数据的容器**object（data）**和一个指向下一个保存数据的容器的地址**next**组成。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NTE5MDQx_size_16_color_FFFFFF_t_70][]

什么叫带环，或者有回环呢？

比如**当前节点**的**next**指向**当前节点之前**的**任意一个节点**的**地址****，那么我们说这个单向链表有回环。或者带环。**

**1.那么如何判断一个单向链表有环呢？**

> 虽然网上有很多博客都说教式的阐述了如何判断是否有环，但我觉得大多都写得很烂。所以我决定自己写一篇。让自己深刻一遍。
> 
> **我们先思考怎样才算有环，或者有环的条件？**
> 
> 我们大脑里要有一个有环的单向链表结构。这里我们看**当一个单向链表中只要有两个节点的next指向同一个节点的地址时，是不是就是有环了**。如何理解这句话，如下图，绿色线代表一个**回环**，P节点为连接点，我们看是不是**a1和a2指向同一个P节点**时，这个单向链表就是有回环的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NTE5MDQx_size_16_color_FFFFFF_t_70 1][]

当我们找出了问题的根本，再来看其他的博客时，就会好理解得多了。

**2.为什么其他博客中会说到一个走的快的指针和一个走的慢的指针，当他们指向同一个节点时，就代表这个单向链表有环了？**

> 操场跑道是一个环对吧。当从学校宿舍到跑道的路程当做还未进入环的链表节点，跑道就是链表的回环，一个跑的快，一个跑的慢，跑的慢的将永远追不上跑的慢的，但是一旦进入的跑道，或者链表回环，那么一旦跑的快的超过慢的一个回环的路程后，他们就相遇了。这就能证明这个链表有回环。速度不同，相遇<===>有回环  ， 速度不同，不相遇<===>无回环。因为我们先确定两个指针速度不同，那么根据是否相遇 就能确定是否有回环了。这是结论。

**3.重中之重！为什么要规定慢的走一步，而快的走两步？而不是慢的一步，快的三步，或者其他？**

> 这算是判断链表是否有环的问题最重要的一个规则了，百分之99的博客只说了结**“****慢的走一步，而快的走两步”**，并未说为什么，这里我们来思考为什么。如下图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NTE5MDQx_size_16_color_FFFFFF_t_70 2][]

有6个节点的一个回环。A快指针每次走3步，B指针每次都一步。

当B慢指针进入回环的**1**位置时，A指针在4位置。

当B慢指针在**2**位置时，A快指针在**1**位置。（这就是上图示例的位置）

当B慢指针在**3**位置时，A快指针在**4**位置。

当B慢指针在**4**位置时，A快指针在**1**位置。

当B慢指针在**5**位置时，A快指针在**4**位置。

当B慢指针在**6**位置时，A快指针在**1**位置。

当B慢指针在**1**位置时，A快指针在**4**位置。（此时已经和刚进入圈的时候位置一样了）

当B慢指针在**2**位置时，A快指针在**1**位置。

当B慢指针在**3**位置时，A快指针在**4**位置。

如果你细心发现他们永远不会相遇，A与B指针永远不会在同一个位置。

**那么为什么呢？？？**

我们还是来思考两个指针走过的节点数相差的节点数量。是不是只有两个指针相差0个节点，6个节点，12个节点，18个....节点的时候他们才会相遇。想象操场，快的比慢的超过1圈的距离，2圈的距离，3圈的距离时，才会相遇。那么如果快的和慢的一个走3步一个走一步，如果开始位置不同，一个1一个2，那么他们永远是（2,5,)（3,8）（4,11）（5,14）（6,17）

相差的数量为：3，5，7，9，11，13，14....大于6的减去回环6，那么他们永远相差3,5,1,3,5,1.....永远不会相差6的倍数个。

**4.那么快的走2步，慢的走1步有什么不同？**

**还是从相差的节点数量来考虑。不论开始相差几个，比如开始进入回环的时候，一个是1一个是5，**

**那么情况是**（1,5,)（2,7）（3,9）（4,11）（5,13）...

相差位置为4,5,6,7,8.....

相信聪明的你已经知道为什么要求快的走2步，慢的走一步了？因为只有这样，不论你的回环是多少节点组成，两个节点相差的距离中间只要不漏掉任何一个相差数额，最后总会等于回环的节点数，而当相差的距离等于回环数的时候就是他们相遇的时刻。就是快的超过慢的一圈或者n圈的时刻。

这就是为什么要求**快的走2步，慢的走1步的原因。**

**其他那些博客写的啥玩意，看也看不懂一堆公式扔给你也不告诉你为什么。气     \_(:з」∠)\_**

**既然知道里原理，实现代码就好写了。**

Java代码实现：

public class test{
        public boolean hasCycle(ListNode head){
            ListNode slow,fast;//定义快慢指针
            slow=fast=head;//同一起跑线
            while(fast!=null&&fast.next!=null){//当有指针指向null时，说明到尾结点了，说明此链表无环
                slow=slow.next;//走一步
                fast=fast.next.next;//走两步
                if(fast==slow){//相遇
                    return ture;
                }
            }
            return false;
        }
    }
    
    //单向链表的一个节点
    public class ListNode{
        int value;//博客里说装数据的地方
        ListNode next;//下一个节点的地址
        ListNode(int x){//本节点构造器
            value=x;//头节点
            next=null;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NTE5MDQx_size_16_color_FFFFFF_t_70]: /images/20211018/ce9aa76cf72c467c995dc0dbf5bd8777.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NTE5MDQx_size_16_color_FFFFFF_t_70 1]: /images/20211018/9152c71de237450881d81bde1a3edf90.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NTE5MDQx_size_16_color_FFFFFF_t_70 2]: /images/20211018/d1710e0b17da496681749a69cc39aaab.png