一、断链表是否为带环链表

首先需要知道链表是否为空，如果不为空，则继续判断。

思路：
定义两个快慢指针，让他们一直移动，如果最终快指针=慢指针，这说明在这个链表中必然存在环。

如果是非带环链表，那么快指针到最后一定是null

是否是带环链表思路图如下：

左边浅黄色为慢指针slow，右边浅绿色为快指针fast，一开始都在头部

第一次：

第二次：

第三次：

第四次：

此时fast和slow相遇，说明是带环链表

实现代码：

public class test {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        //fast先到达链表末尾，链表末尾下一个指向为null，则不是带环链表
        while(fast != null && fast.next != null){ 
            fast = fast.next.next;  //fast走两格
            slow = slow.next;  //slow走一格
            if(fast == slow){  //当fast与slow相遇
                return true;   //说明该链表为带环链表
            }
        }
        return false;
    
    }
}

二、带环链表的环入口

带环链表入口思路图：

此时相遇，只需要把slow重新放到头部

让fast和slow都只走一步



slow和fast再次相遇，此时位置就是环的入口

实现代码：

public class test{
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;  
            }
        }        
        if(fast == null || fast.next == null){
            return null;
        }
        //上面都是验证是否为带环链表
        slow = head;  //slwo放回头部head
        while(fast != slow){ //没相遇就一直走，到再次相遇为止
            slow = slow.next;
            fast = fast.next;    
        }
        return slow;
       
    }
}