检测链表是否有环

本文主要是介绍检测链表是否有环，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 如何检测一个链表是否有环

具体步骤如下：

（1）定义两个指针 fast（快指针）与 slow（慢指针），二者的初始值都指向链表头；
（2）slow 每次前进一步，fast 每次前进两步，两个指针同时前进；
（3）快指针每移动一次都要跟慢指针比较，直到快指针等于慢指针为止，就证明这个链表是带环的单向链表，否则证明这个链表是不带环的循环链表（fast 先行到达尾部为 null，则为无环链表）。

具体实现如下：

 public boolean isLoop(Node head) {Node fast = head;Node slow = head;if(fast == null)return false;while(fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if(fast == slow){return true;}}return !(fast == null || fast.next == null);}

上述方法只能判断链表是否有环，但不能判断环的位置。

2. 如何找到换的入口点

为了判断环的位置，我们需要找到换的入口点，那么如何找到换的入口点呢？

如果单链表有环，按照上述思路，当 fast 与 slow 相遇时， slow 指针肯定没有遍历完链表，而 fast 指针已经在环内循环了 n ( n >= 1 ) 圈。

这里写图片描述

假设 slow 指针走了 s 步，则 fast 指针走了 2s 步（fast 步数还等于 s 加上在环上多转的 n 圈）。设环长为 r，则满足如下关系表达式：

            2s = s + nrs = nr

设整个链表而长度为 L，入口环与相遇点的距离为 x，起点到环入口的距离为 a, 则满足如下表达式：

         a + x = nra + x = (n-1)r + r = (n-1)r + L-aa = (n-1)r + (L-a -x)

(L - a - x) 为相遇点到环入口的距离，从链表头到环入口点等于（n - 1）循环 + 相遇点到环入口点。

经过上面的分析，可以总结该方法的步骤为：

（1）找到相遇点，并标记为 fast；
（2）在链表头也设置一个指针 slow;
（3）fast 和 slow 指针一起前进，每次各走一步，两个指针必定相遇。且相遇第一点为环入口点。

具体实现如下：

public Node findLoopPort(Node head) {Node slow = head;Node fast = head;while(fast != null && fast.next != null) {// 先找到相遇点slow = slow.next;fast = fast.next.next;}if(fast == null || fast.next == null)return null;slow = head;while(slow != fast) {//slow 从头开始和相遇点 fast 一起向前移动slow = slow.next;fast = fast.net;}return slow;
}