Java教程
Floyd 判圈算法
- 以下是引用 wiki 的介绍：
- 个人的理解：
- 1、演示
- 下面进行演示。假设头节点为0，第六号节点的子节点为第2号节点，所以有 2->3->4->5->6->3 成环。设 t 与 h 在环内相遇于 A 点
- 2、求环内交点
- 3、求环入口
- 4、求环长度
- 5、代码汇总
Floyd判圈算法
以下是引用 wiki 的介绍：
Floyd判圈算法(Floyd Cycle Detection Algorithm)，又稱龜兔賽跑算法(Tortoise and Hare Algorithm)，是一個可以在有限狀態機、迭代函數或者鍊表上判斷是否存在環，求出該環的起點與長度的算法。
如果有限狀態機、迭代函數或者鍊表存在環，那麼一定存在一個起點可以到達某個環的某處(這個起點也可以在某個環上)。
初始狀態下，假設已知某個起點節點為節點S。現設兩個指針t和h，將它們均指向S。
接著，同時讓t和h往前推進，但是二者的速度不同：t每前進1步，h前進2步。只要二者都可以前進而且沒有相遇，就如此保持二者的推進。當h無法前進，即到達某個沒有後繼的節點時，就可以確定從S出發不會遇到環。反之當t與h再次相遇時，就可以確定從S出發一定會進入某個環，設其為環C。
如果確定了存在某個環，就可以求此環的起點與長度。
上述算法剛判斷出存在環C時，顯然t和h位於同一節點，設其為節點M。顯然，僅需令h不動，而t不斷推進，最終又會返回節點M，統計這一次t推進的步數，顯然這就是環C的長度。
為了求出環C的起點，只要令h仍均位於節點M，而令t返回起點節點S，此時h與t之間距為環C長度的整數倍。隨後，同時讓t和h往前推進，且保持二者的速度相同：t每前進1步，h前進1步。持續該過程直至t與h再一次相遇，設此次相遇時位於同一節點P，則節點P即為從節點S出發所到達的環C的第一個節點，即環C的一個起點。
个人的理解：
开始时，t与h都位于头节点，每次h先移动2单位，之后判断h是否与t在同一点内，若不在，则轮到t移动一单位；若在同一点，则说明存在一个环。否则如此往复，h一定会移动到链表的尾端，即无法再移动，这种情况便是不存在环的情况。
1、演示
下面进行演示。假设头节点为0，第六号节点的子节点为第2号节点，所以有 2->3->4->5->6->3 成环。设 t 与 h 在环内相遇于 A 点
至于为什么有环会相遇，这点很好理解。想象两个不同速度的人在操场上跑步。即使慢的人领先与快的人，到最后快的人也会追上慢的人。
2、求环内交点
现在来说明一下，为什么如果有环的话，为什么快指针会在一圈之内追上慢指针。
已知 t(慢指针) 的速度为 1/s h(快指针) 的速度为 2/s 假设在 t 刚入环时，h 在环内的位置距离入环点的距离为 b，设 环长度为 L。 则此时 h 与 t之间的距离（追赶距离）为 L - b 而 h 与 t 的相对速度为：(2-1)/s，也就是每一个周期，h与t的距离都会缩短一个单位 所以，当 h 与 t 相遇时，他们所想好的时间为：(L-b)/(2-1) = (L-b)/s 由于t的速度为1/s 所以，t 与 h 相遇时，t所走的距离为(L-b) 上式中，仅当 b=0 时 t 需要走一圈之后才能与h相遇，但 b=0 这条件是不存在的 若 b=0 这存在，这说明，t刚好追赶上h时是在入环口。 但这很明显是不可能的，起始时h先手走两单位，之后才到t移动一单位。因此在不存在环的情况下， t 永远追及不到 h（这也是判断是否有环的思路） 所以，L-b 一定小于 L 即h在环内可以在一圈之内追及上t
/**
*求环内交点
* @param head 头节点
* @return 如果存在环，则返回环内快慢指针相交的节点；若无则返回null
*/
public static ListNode FindIntersection(ListNode head) {
ListNode h = head, t = head;
while (h != null ) {
if (h.next != null) {
h = h.next;
t = t.next;
}
else {
return null;
}
if (h.next != null) {
h = h.next;
//每次h跑完两步就要检查一下是否追上了t，这里可能会有人有疑问，为什么上面h刚跑完之后不检查是否追上了t
//这是因为，后面需要根据这个点来求入环点，而推导公式的基础便是每次h行动2单位都是不可分割的。
if (t == h) {
return t;
}
}
}
return null;
}
3、求环入口
如上图，设环外长度为a，h与t相交于环内的A点，其距离入环口的距离为b，一圈长度为 C
由上面的现在来说明一下，为什么如果有环的话，为什么快指针会在一圈之内追上慢指针。可知，相遇时，t在环内走过的距离不会超过一圈
- 则 t移动的距离为：Lt = a + C*0 + b
- 则 h移动的距离为：Lh = a + C*n + b
- 由于h移动的总距离为t的两倍，则有 Lh-Lt = Lt =
(a + C*0 +b ) - (a + C*n + b) = C*n
所以可见 Lt 为环长的整数倍。
现在让 t 指针回到头节点，h 指针保持在 A 点，然后 两指针同步的一起移动 a 单位（其中t指针的作用是贡献 a 长度，使其与环内的已有长度 b 的 h 构成刚好一个环的长度）到达环入口。由于一开始 h 在环内距离入环点的距离为 b ，所以当 t 移动了 a 单位时，h在环内的长度为 b + a = Lt 所以此时 h 也刚好到达环入口（想一下，从一个地方进入操场跑一圈当然是会回到入口点的）。
所以当 t 与 h相交时便是环的入口。
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode intersListNode = FindIntersection(head);
if (intersListNode != null) {
while (head != intersListNode) {
head = head.next;
intersListNode = intersListNode.next;
}
return head;
} else {
return null;
}
}
4、求环长度
当找到环内交点时，令其中指针一个不动，而另一个指针每次移动一单位。最后再次相遇时所走过的距离便是环的长度。
/**
*
* @param intersListNode 循环圈内 快慢指针的交点
* @return 一个圈的长度
*/
public static int LoopLength(ListNode head ,ListNode intersListNode) {
int cnt = 0;
//无环的情况
if (intersListNode == null)
return cnt;
//无环外长的情况
if (head == intersListNode) {
cnt++;
head = head.next;
while (head != intersListNode && cnt++>0)
head = head.next;
}
//有环外长的情况
else {
ListNode t = intersListNode.next;
cnt++;
while (t != intersListNode && cnt++>0)
t = t.next;
}
return cnt;
}
5、代码汇总
import java.util.ArrayList;
import java.util.HashMap;
// Definition for singly-linked list.
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode intersListNode = FindIntersection(head);
if (intersListNode != null) {
while (head != intersListNode) {
head = head.next;
intersListNode = intersListNode.next;
}
return head;
} else {
return null;
}
}
/**
*
* @param head 头节点
* @return 如果存在环，则返回环内快慢指针相交的节点；若无则返回null
*/
public static ListNode FindIntersection(ListNode head) {
ListNode h = head, t = head;
while (h != null ) {
if (h.next != null) {
h = h.next;
t = t.next;
}
else {
return null;
}
if (h.next != null) {
h = h.next;
//每次h跑完两步就要检查一下是否追上了t，这里可能会有人有疑问，为什么上面h刚跑完之后不检查是否追上了t
//这是因为，后面需要根据这个点来求入环点，而推导公式的基础便是每次h行动2单位都是不可分割的。
if (t == h) {
return t;
}
}
}
return null;
}
/**
*
* @param intersListNode 循环圈内 快慢指针的交点
* @return 一个圈的长度
*/
public static int LoopLength(ListNode head ,ListNode intersListNode) {
int cnt = 0;
//无环的情况
if (intersListNode == null)
return cnt;
//无环外长的情况
if (head == intersListNode) {
cnt++;
head = head.next;
while (head != intersListNode && cnt++>0)
head = head.next;
}
//有环外长的情况
else {
ListNode t = intersListNode.next;
cnt++;
while (t != intersListNode && cnt++>0)
t = t.next;
}
return cnt;
}
/**
*
* @param enm 链表的前后驱节点的关系
* @param head 头节点
* @return 尾结点
*/
public static ListNode init(int[][] enm, ListNode head) {
HashMap<Integer, ListNode> map = new HashMap<Integer, ListNode>();
ListNode t = head;
map.put(0, head);
for (int i = 0; i < enm.length; i++) {
ListNode node;
if (map.containsKey(enm[i][1])) {
node = map.get(enm[i][1]);
}
else {
node = new ListNode(enm[i][1]);
map.put(enm[i][1], node);
}
t.next = node;
t = node;
}
return t;
}
public static void main(String[] st) {
ListNode head = new ListNode(0);
Solution ss = new Solution();
// int[][] enm = { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 3, 4 }, { 4, 5 }, { 5, 6 }, { 6, 3 } };
int[][] enm = { { 0, 1 }, { 1, 0}};
init(enm, head);
System.out.println(LoopLength(head, FindIntersection(head)));
System.out.println(ss.detectCycle(head).val);
}
}
-
Springboot应用的多环境打包入门11-23
-
Springboot应用的生产发布入门教程11-23
-
Python编程入门指南11-23
-
Java创业入门：从零开始的编程之旅11-23
-
Java创业入门：新手必读的Java编程与创业指南11-23
-
Java对接阿里云智能语音服务入门详解11-23
-
Java对接阿里云智能语音服务入门教程11-23
-
JAVA对接阿里云智能语音服务入门教程11-23
-
Java副业入门：初学者的简单教程11-23
-
JAVA副业入门：初学者的实战指南11-23
-
JAVA项目部署入门：新手必读指南11-23
-
Java项目部署入门：新手必看指南11-23
-
Java项目部署入门：新手必读指南11-23
-
Java项目开发入门：新手必读指南11-23
-
JAVA项目开发入门：从零开始的实用教程11-23
