龟兔赛跑之-如何判断链表有环?
程序员文章站
2022-11-02 18:43:23
** * @Author: Kerven Han * @Date: * @Describe: 经典的快慢指针的使用案例 */public class LinkListHasCycle { public static boolean judgeHasCycle(LinkNode head) { //空或者单 就返回false if (null == head || null == head.getNext()) { return....
**
* @Author: Kerven Han
* @Date:
* @Describe: 经典的快慢指针的使用案例
*/
public class LinkListHasCycle {
public static boolean judgeHasCycle(LinkNode head) {
//空或者单 就返回false
if (null == head || null == head.getNext()) {
return false;
}
//龟兔都是同一个起点,保证公平
LinkNode fast = head;
LinkNode slow = head;
//开始比赛,进入循环判断,注意结束循环的条件
//有任何一个指针遍历到了最后为null都说明了链表是没有环的被遍历完了
//既然fast走的快那么难道不是它达到null的时候我们就可以认定链表是没有环的吗,因为如果有环的话就会一直在环里转圈就不会有结束
while (fast != null && fast.getNext() != null) {
//注意:这里是我们要不断的移动fast slow 这两个指针,千万别写成了head 而是要写成fast slow
//因为head 是你传入的参数,他是不变的,但是fast slow 这个两个指针是不断的往后移动的。
fast = fast.getNext().getNext();
slow = slow.getNext();
//两者相遇了,因为只要有环,且两者速度不同步,那么可想而知,总有一刻跑的快的一定会追上跑得慢的,
//可以联想一下运动会的时候,你和一个体育生同场跑1500米的时候,他真的有可能领先你一圈,这里是同理。
if ( fast == slow ) {
return true;
}
}
return false;
}
}
public class LinkNode {
private int data;
private LinkNode next;
public LinkNode(int data){
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public void setNext(LinkNode next) {
this.next = next;
}
public LinkNode getNext() {
return next;
}
}
本文地址:https://blog.csdn.net/weixin_36630761/article/details/107691509
上一篇: 浅析地方门户网站内容建设与推广三要素