算法——Floyd判圈算法

本文主要是介绍算法——Floyd判圈算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

介绍

Floyd判圈算法用于判断一个链表中是否有环。

思想

使用快慢指针fast, slow，快指针每次走两步fast = fast.next.next，慢指针每次走一步slow = slow.next。当出现fast == null || fast.next == null时，说明链表不存在环，如果存在环，则快指针永远不可能指向null；当出现fast == slow时，说明链表存在环，此时让慢指针回到原点，然后让两个指针的速度相同，每次都只走一步fast = fast.next; slow = slow.next;，它们再次相遇的点就是环的入口。

论证

对于上面的这张图，不妨设两个指针在点R处第一次相遇，此时让慢指针回到链表头部点P处，让快慢指针同速，每次只走一步，直到第二次相遇。注意，指针在环上是逆时针走的。

第一次相遇时，有 $$2t=s_{fast}=|PQ|+mC+\stackrel{⌢}{\mathrm{QR}}$$ $$t=s_{slow}=|PQ|+nC+\stackrel{⌢}{\mathrm{QR}}$$ 其中$s_{fast}$是第一次相遇前快指针走的距离，$s_{slow}$是第一次相遇前慢指针走的距离，$|PQ|$是点$P$和点$Q$之间的距离（也就是链表的起点到环的入口的长度），$m$是第一次相遇前快指针绕环转的圈数，$n$是第一次相遇前慢指针绕环转的圈数，$C$是环的周长，$\stackrel{⌢}{\mathrm{QR}}$是从点$Q$沿环逆时针到点$R$的距离，$t$是移动的次数（快指针每次走两步，慢指针每次走一步）。

用第一个式子减去第二个式子，得 $$t=(m-n)C$$ 再将第三个式子带入第二个式子可得 $$|PQ|+\stackrel{⌢}{\mathrm{QR}}=(m-2c)C$$ 也就是说$|PQ|$与$\stackrel{⌢}{\mathrm{QR}}$的和为环的周长的整数倍，从而可知$|PQ|$就是从点$R$沿环逆时针到点$Q$的距离$\stackrel{⌢}{\mathrm{RQ}}$，即有$|PQ|=\stackrel{⌢}{\mathrm{RQ}}$。

现在考虑第一次相遇与第二次相遇之间的事情，慢指针从链表头部（点$P$）开始遍历，快指针从第一次相遇的点（点$R$）开始遍历，慢指针的路程是$|PQ|$，快指针的路程是$\stackrel{⌢}{\mathrm{RQ}}$，由上面的证明$|PQ|=\stackrel{⌢}{\mathrm{RQ}}$可知：它们的第二次相遇点就是环的入口$Q$。

从而当两个指针第二次相遇时，它们指向的点就是环的入口得证。

代码

对链表节点的定义如下：

class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}
}

判断链表是否有环的代码如下：

public class Solution {public boolean hasCycle(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (slow == fast) {return true;}}return false;}
}

求环的入口的代码如下：

class Solution {public ListNode detectCycle(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (slow == fast) {slow = head;while (slow != fast) {slow = slow.next;fast = fast.next;}return slow;}}return null;}
}

这篇关于算法——Floyd判圈算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---