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

JAVA 快慢指针

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        //申明快慢指针
        ListNode fast = pHead,slow = pHead;
        boolean flag = false;
        //判断是否有环
        //如果是环形的链表就没有null节点，fast和slow一定会相遇
        //如果不是环形链表fast会走完链表直到null节点出while循环。
        while(fast !=null && fast.next !=null){
            slow = slow.next; //slow走一步
            fast = fast.next.next; //fast走两步
            if(slow == fast) break;
        }
        //两种情况会走到这里，一种是有环快慢相遇，一种是无环，fast.next为null
        if(fast ==null || fast.next == null) return null; //无环 fast.next
        //有环,快指针到头节点，然后和慢指针一起走
        fast = pHead;
        //相遇的地方就是环的入口
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}