判断链表是否有环，找环的起点（双指针）

判断链表是否有环，找环的起点（双指针）

LeetCode141
题目描述：

一般的单链表是没有环的，也就是说链表的尾节点指向null，而环形链表一直追溯next可以遍历到相同的值，且没有节点的next指向null。判断链表是否有环可以采用双指针方法，定义一个慢指针slow和一个快指针fast，慢指针每次走一步，快指针每次走两步，那么快指针如果和慢指针相遇了就说明链表有环。

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) return true;
        }
        return false;       
    }
}

那么如果还需要找到入环的头节点呢？这就需要一点技巧了。

这个题在LeetCode142

先上代码：

         if(fast == slow){ //有环
                slow = head;
                while(slow != fast){
                slow = slow.next;
                fast = fast.next;
                }
                return slow; 
           }  

在确认有环之后，只要让任意一个节点回到起点，然后同时移动两个节点，当节点再次相遇时，所在的位置就是入环的位置。为什么呢？
假设第一次相遇slow节点前进了k步，那么fast节点应该移动了2k步，k就是环的长度。

那么此时让slow节点回到头部，slow和fast同时移动，假设第一次相遇点距离环起点的长度为m，那么对于slow来说，第二次移动了k-m，对fast来说也是移动了k-m,也就是说相遇的点恰好是环的起点。

整体代码：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){ //有环
                 slow = head;
                 while(slow != fast){
                 slow = slow.next;
                 fast = fast.next;
                 }
                 return slow; 
            }  
        }
        return null;       
    }
}

参考文章：https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247484505&idx=1&sn=0e9517f7c4021df0e6146c6b2b0c4aba&chksm=9bd7fa51aca07347009c591c403b3228f41617806429e738165bd58d60220bf8f15f92ff8a2e&scene=21#wechat_redirect