欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

龟兔赛跑之-如何判断链表有环?

程序员文章站 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

相关标签: 算法