1.判断给定的链表中是否有环。如果有环则返回true，否则返回false。牛客题目

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
/*
首先，slow指针和fast指针都会进入环内，就像在环形跑道内不同位置的两个人。slow指针在后面，fast指针在前面，但实际上fast指针也在追slow指针，希望能超slow指针一圈。那么fast指针总会追上slow指针的。那么fast指针会不会跳过slow指针呢？不会的，因为fast每次走2步，slow每次走1步，假设两者在环内的距离差为N，
那么每次走动，距离差N都会缩小一步，
因为fast与slow指针的步长差是1。最终，N会减少到0，也就是两者会相遇。
但是，如果fast和slow的步数差不是1，是2（或3、4......），距离差N不保证是2的倍数，也就是说fast赶上slow时不一定会相遇
*/

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null) return false;
        ListNode fast,slow;
        fast = head;//起点相同
        slow = head;
        while(fast != null && fast.next != null){//当不是环时（或者相遇时），退出循环
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow){
                return true;
            }
        }
        return false;//不是环（fast.next = null）
    }
}

2.给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。牛客题目
参考解析

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

    ListNode(int val) {
        this.val = val;
    }
}
*/
/*
由上个题可知，当设置fast步数是slow的两倍时，fast一定能追上slow且相遇（距离差为N，fast和slow每移动一次，距离差减小1）

如果有环，一定有入口。
如果有环，设置f是s的两倍，一定会相遇
所有如果没有相遇点，说明没有环，也不可能有入口。
1.先找相遇点
2.没有相遇点则false
3.找到相遇点再找入口


*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode fast,slow,meet;
        fast = pHead;//起点相同
        slow = pHead;
        meet = null;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                meet = fast;
                break;
            }
        }
        if(meet == null){
            return null;
        }
        slow = pHead;
        while(slow != meet){
            slow = slow.next;
            meet = meet.next;
        }
        return slow;
    }
}