剑指offer-55

检查有没有环，用快慢指针，快指针一下进两步，慢指针一下进一步，如果有环，两指针一定会相遇，如果没有环，快指针肯定有一个会指空。
判断有环了，刚刚相遇的那个点肯定在环内，从那个点把环切开，形成一个交叉链表，环的入口即是交叉链表的第一个交点。遍历两条链表，然后求长度差，长的链表的指针先走长度差步，然后和短的链表的指针一起走，指针相等时即为第一个交点。

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

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

    public ListNode EntryNodeOfLoop(ListNode pHead){
        if(pHead==null||pHead.next==null){
            return null;
        }
        ListNode fast = pHead.next;
        ListNode slow = pHead.next.next;
        while(fast!=slow){
            if(slow==null||fast==null||fast.next==null){
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode end = slow;
        ListNode start1 = pHead;
        ListNode start2 = slow.next;
        int l1 = 0;
        while(start1!=end){
            l1++;
            start1 = start1.next;
        }
        int l2 = 0;
        while(start2!=end){
            l2++;
            start2 = start2.next;
        }
        start1 = pHead;
        start2 = slow.next;
        if(l1>l2){
            int num = l1-l2;
            while(num>0){
                start1 = start1.next;
                num--;
            }
        }else {
            int num = l2-l1;
            while(num>0){
                start2 = start2.next;
                num--;
            }
        }
        while(start1!=start2){
            start1 = start1.next;
            start2 = start2.next;
        }
        return start1;

    }
}