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

**
 * @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