剑指offer - 链表中环的入口结点

题目链接：https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&&tqId=11208&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  快慢指针：定义两个指针，这两个指针移动的速度一快一慢，一般情况下，快指针的移动步长是慢指针的两倍。显然我们可以知道，如果链表中有环那么快慢指针一定会相遇。如果有环，让其中一个指针指向头指针，然后这两个指针每次走一步，那么它们第一次相遇的点即为链表的入口结点。环的入口结点看下面图中的分析。

/*
 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;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) { // 有环
                flag = true;
                break;
            }
        }
        if (!flag) return null;
        slow = pHead; //有环
        while (slow != fast) { // 找到入口结点
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}