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
喜欢就支持一下吧
相关推荐