正面刚算法-检测链中是否有环

检测链表中是否存在环

通俗的讲检测链中的环就是看这个链表的遍历是否进入到一个环中，如果进入到环中，则会出现死循环，next指针永远不为空。

检测链表中是否存在环有两个思路

• 保存遍历指针走过的每一个地址，如果next指针指向的地址曾经被遍历过，则该链存在环
• 使用两个指针，慢指针每次访问next节点，快指针访问next的next节点，如果存在环，则快指针一定会在环中的第一次循环中与慢指针重逢。

在解决这个问题中，编写链表中检测环代码并不复杂，复杂的点在于如果使用快慢指针检测环，理解快慢指针。

快慢指针

指针操作

每次快指针比慢指针多”走“一步，当快指针指向的地址和慢指针指向的地址相同时，则该链存在环。

快慢指针使用疑惑点

当初比较疑惑的是，如果把链上的每个结点比作方格的话，快指针每次跳两格方格，慢指针跳一个方格。如果存在环，快指针会进入环中第一次循环时在某个方格中相遇。我当时有点疑惑，如果存在环，快指针可以“追上”慢指针是一定的，但是快指针每次跳两个方格，慢指针跳一个方格。如果快指针在环中的第一次循环中，快指针跳过的方格是慢指针跳后所在的方格，那为什么必定在第一次循环中会在同一个方格“相遇”呢？

分解追击问题

有一个例子可以很好的理解这个“追击”过程。

1. 情景一:当快指针和慢指针在紧邻的两个方格中时，进行跳跃，慢指针跳一个方格，快指针跳两个方格，结果是快、慢指针会跳进同一个方格；

   
   快慢指针差一格

2. 情景二：那就是当快指针和慢指针中间差一个方格的时候，进行跳跃，慢指针跳一个方格，快指针跳两个方格。完成第一次跳跃后，快指针紧邻慢指针(场景同情景一)，进行第二次跳跃；结果为快、慢指针跳进同一个方格；

   
   快慢指针差两格

3. 情景三：快、慢指针中间差两个方格，进行第一次跳跃，慢指针跳一个方格，快指针跳两个方格。完成第一次条约后，快指针和慢指针差一个方格（同场景二）；进行第二次跳跃，结果同场景一，进行第三个跳跃，结果为快、慢指针跳进同一个方格；

   
   快慢指针差三格

4. 场景N:快、慢指针中间差N个方格，进行N次跳跃，快指针紧邻慢指针，在进行一次跳跃，则两指针重逢。

结论

通过上面的模拟，我们可以发现，如果存在环的情况下，快指针一定会在环中第一次循环中与慢指针重合，我们可以用相对“速度”来理解快、慢指针。快指针相对于慢指针，每次只移动一格，此时每次移动，快指针和慢指针间隔减少1；所以快指针必然会追上慢指针并重合。

代码实现

我们理解了快慢指针的使用，写出快慢指针代码就so easy了！我们只需要不断访问快、慢指针的指向地址，比较两个地址即可；不过不要忘记边界值的判断处理！

    public static Boolean checkLoop(Node head) {

        if (null == head) return false;

        Node fast = head, slow = head;

        while (null != slow.next && null != fast.next && null!= fast.next.next){
            slow = slow.next;
            fast = fast.next.next;
            System.out.println(String.format("fast:%s slow:%s",fast.data,slow.data));
            if (fast == slow){
                return true;
            }
        }

        return  false;
    }

当对快慢指针理解的话，写出代码就像写中文描述一样简单！

github代码链接