2021/04/22
前言

如下链表是一个带环链表,环的入口是 2,环的长度为 4。

链表节点定义如下:
// 单链表节点定义,参考 Leetcode
class ListNode<T> {
public T val;
public ListNode<T> next;
public ListNode(){
this(null,null);
}
public ListNode(T val){
this(val,null);
}
public ListNode(T val, ListNode next){
this.val = val;
this.next = next;
}
}
复制代码
判断链表是否有环
判断链表是否有环,比较好的方法是 快慢指针法。
定义两个指针 fast, slow ,初始都指向头节点。快指针 fast 一次向后移动一位,慢指针 slow 一次向后移动两位;如果快慢指针相遇(指向同一个节点且都不为空),说明链表存在环。
// 判断链表是否有环
public boolean isLoop(){
if(this.head == null){
return false;
}
ListNode<T> fast = head;
ListNode<T> slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
return true;
}
}
return false;
}
复制代码
确定环入口
如果链表存在环,如何确定环的入口(环交汇的节点)是哪个节点?
假设链表环的入口为 entrance ,快慢指针相遇的节点为 meet,由于快指针的速度是慢指针的 2 倍,所以当快慢指针相遇时,慢指针走过的距离为 s,则快指针走过的距离为 2s。
假设头节点到环入口的距离为 he,环入口到相遇节点的距离为 em,环的长度为 r。

我们可以得到:
© 版权声明
文章版权归作者所有,未经允许请勿转载。
THE END
喜欢就支持一下吧
相关推荐





















![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)

![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)