判环算法01
检验链表是否有环
//判断环
public boolean hasCycle(ListNode head){
ListNode p1=head;//乌龟
ListNode p2=head;//兔子
while (p2!=null&&p2.next!=null){
p1=p1.next;
p2=p2.next.next;
if(p1==p2){
return true;
}
}
return false;
}
思路:利用了快慢指针的原理,快的只要与慢的相遇,就代表终究是一个圆环
判断环的位置02
public ListNode hasCycle(ListNode head){
ListNode p1=head;//乌龟
ListNode p2=head;//兔子
while (p2!=null&&p2.next!=null){
p1=p1.next;
p2=p2.next.next;
if(p1==p2){//第一次遇见
p1=head;//乌龟返回初始值
while (true) {
if (p1==p2) {//再次相遇
return p1;
}
p1=p1.next;
p2=p2.next;
}
}
}
return null;
}
原理:总结规律
从起点开始走,走a+绕环n圈,都能找到环的入口位置
兔子走的:a的直线路程+绕环n圈+K
乌龟走的:a的直线路程+绕环n圈+K
兔子走的距离是乌龟的两倍
兔子走的减去乌龟走的 n
乌龟走的:兔子走的-乌龟走的=绕环圈数
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
