目录
本文主要介绍以环形链表相关的算法，主要采用Java语言实现，这类算法又称Floyd's Tortoise and Hare Algorithm （Floyd 龟兔赛跑算法），不得不说，这个原理挺神奇的就解决了，环形链表的问题。
注意：以下代码有关链表的算法实现均基于以下链表节点类：
//链表节点类
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}龟兔算法动画来自：
Floyd's Hare and Tortoise Algorithm Demo - One Step! Code
相关教程：
一、龟兔赛跑算法
如果链表上存在环，那么在环上以不同速度前进的两个指针必定会在某个时刻相遇（如上图所示）。算法分为两个阶段。
1.1 阶段1
-
龟一次走一步，兔子一次走两步
-
当兔子能走到终点时，不存在环
-
当兔子能追上龟时，可以判断存在环
存在环情况：（上帝视角）
不存在环情况：（上帝视角）
1.2 阶段2
-
从它们第一次相遇开始，龟回到起点，兔子保持原位不变
-
龟和兔子一次都走一步
-
当再次相遇时，地点就是环的入口
a.第一次相遇：（证明已经是环）
b.龟回到起点，兔子保持原位不变：
c.再次相遇：再次相遇的位置为环入口
！！！！！！
1.3 为什么呢？
********精髓之处********
-
设起点到入口走 a 步（本例是 7），绕环一圈长度为 b（本例是 5），
-
那么从起点开始，走 a + 绕环 n 圈，都能找到环入口
-
第一次相遇时
-
兔走了 a + 绕环 n 圈（本例 2 圈） + k，k 是它们相遇距环入口位置（本例 3，不重要）
-
龟走了 a + 绕环 n 圈（本例 0 圈） + k，当然它绕的圈数比兔少
-
兔走的距离是龟的两倍，所以龟走的 = 兔走的 - 龟走的 = 绕环 n 圈
-
-
而前面分析过，如果走 a + 绕环 n 圈，都能找到环入口，因此从相遇点开始，再走 a 步，就是环入口
-
实在不理解的话，可以理解为快慢指针，遵循以上结论
知晓了龟兔算法的精髓后，下来解决这两个经典问题！
二、判断是否有环
2.1 问题描述
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false
2.2 示例
示例一：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。示例二：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。示例三：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。2.3 代码实现
public boolean hasCycle(ListNode head) {
ListNode h = head; // 兔
ListNode t = head; // 龟
while (h != null && h.next != null) {
t = t.next;
h = h.next.next;
if(h == t){ // 龟兔相遇时，证明是环
return true;
}
}
return false;
}三、找到环入口
3.1 问题描述
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
3.2 示例
示例一：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。示例二：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。示例三：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。3.3 代码实现
public ListNode detectCycle(ListNode head) {
ListNode t = head; // 龟
ListNode h = head; // 兔
while (h != null && h.next != null) {
t = t.next;
h = h.next.next;
if (h == t) { //证明是环
t = head; //龟回到起点
while (true) {
if (h == t) { //再次相遇即为环入口
return h;
}
h = h.next; //同时前进
t = t.next; //同时前进
}
}
}
return null;
}总结
本文主要介绍了链表算法中经典问题：龟兔赛跑算法，主要是判断链表中是否有环，以及如何找到环的入口。最重要的是龟兔赛跑算法的两个阶段和背后的原理。并提供了Java代码实现。希望对各位有所帮助，下期见，谢谢~
标签：head,ListNode,pos,next,链表,算法,数据结构,之龟,节点 From： https://blog.csdn.net/weixin_64178283/article/details/143191777