题解 | #链表中环的入口结点#

public class Solution {
    /* 链表中环的入口: 若链表中包含环,找到环的入口
       - 通过遍历到重复元素,找出第一个环元素
       - 快慢指针,只要ab相交,就说明存在环，此时n=2n (a+b = a+b+(b+c)*m)
     法一：哈希表法,每遍历一个就放到哈希表中,直到遇到重复元素
     法二：快慢指针
       1.快慢指针找到相交点
        - 2(a+b) = a+b+(b+c)*m
        - a+b = (b+c)*m
         --> a = (b+c)*(m-1) + c
       2.根据公式找到入环点
         b为当前位置,c为环的剩余节点,
         - 当m为1时(只多转一圈就遇到了)
         - 当m为n时,多转n圈后,走c步遇到
    */
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if(pHead == null)
            return pHead;
        ListNode slow = pHead;
        ListNode fast = pHead;
        
        boolean isLoop = false;
        //快慢指针判断 是否成环
        while(slow.next!=null && fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                isLoop = true;
                break;
            }
        }
        //找到环的入口 2(a+b) = a+b+(b+c)*n -->a=c +(b+c)*(n-1)
        if(isLoop){
            //环的当前位置为b,c为剩余路径
            while(pHead != slow){
                pHead = pHead.next;
                slow = slow.next;
            }
            return slow;
        }else{
            return null;
        }
    }
}