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

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

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

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        /**
         * 我们现在假定已经是一个有环的链表了，那么这个链表中怎么找到环的入口呢？
         * 在慢指针进入链表环之前，快指针已经进入了环，且在里面循环，这才能在慢指针进入环之后，快指针追到了慢指针，
         * 不妨假设快指针在环中走了n圈，慢指针在环中走了m圈，它们才相遇，
         * 而进入环之前的距离为x，环入口到相遇点的距离为y，相遇点到环入口的距离为z。
         * 快指针一共走了x+n(y+z)+y步，慢指针一共走了x+m(y+z)+y，
         * 这个时候快指针走的倍数是慢指针的两倍，则x+n(y+z)+y=2(x+m(y+z)+y)，
         * 这时候x+y=(n−2m)(y+z)，因为环的大小是y+z，
         * 说明从链表头经过环入口到达相遇地方经过的距离等于整数倍环的大小：
         * 那我们从头开始遍历到相遇位置，和从相遇位置开始在环中遍历，会使用相同的步数，
         * 而双方最后都会经过入口到相遇位置这y个节点，那说明这y个节点它们就是重叠遍历的，
         * 那它们从入口位置就相遇了，这我们不就找到了吗？
         * */

        //采用快慢指针法来判断是否有环，一个指针走一步，一个指针走两步，
        // 如果走到了最后，说明无环,如果慢指针追上了快指针，说明有环
        ListNode firstNode = pHead;
        ListNode secondNode = pHead;
        boolean flag = false;
        while (firstNode != null && secondNode != null) {
            firstNode = firstNode.next == null ? null : firstNode.next.next;
            secondNode = secondNode.next;
            //找到了第一次相遇的地方
            if (firstNode != null && firstNode == secondNode) {
                flag = true;
                break;
            }
        }
        if (flag) {
            //找到了环会跳出来,把快指针设置为头，每次走一步
            firstNode = pHead;
            while (firstNode != null && secondNode != null) {
                //找到了第一次相遇的地方
                if (firstNode != null && firstNode == secondNode) {
                    return firstNode;
                }
                firstNode = firstNode.next;
                secondNode = secondNode.next;
            }
        }
        return null;

    }
}