链表中环的入口结点

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

思路

两个快慢指针从头节点开始走，

代码

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

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
     public static void main(String[] args) {
       Solution s = new Solution();
       //定义一个链表
       ListNode p1 = new ListNode(1);
       ListNode p2 = new ListNode(2);
       ListNode p3 = new ListNode(3);
       ListNode p4 = new ListNode(4);
       ListNode p5 = new ListNode(5);
       p1.next = p2;
       p2.next = p3;
       p3.next = p4;
       p4.next = p5;
       p5.next = p3;
       s.EntryNodeOfLoop(p1);
    }

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
       //定义两个快慢指针
        ListNode slow = pHead;
        ListNode fast = pHead;
        if(pHead == null || pHead.next == null) return  null;
        //找出快慢指针相遇的节点
        do {  //这里一定要是do-while；如果是while的话slow永远等于fast
            slow = slow.next;
            fast = fast.next.next;
            if(fast == null || fast.next == null)
                return null;
        }while (slow != fast);
        //找出环入口并打印第几个节点是环入口
        int count = 1;
        slow = pHead;
        while (slow != fast){ // 因为这里slow已经被重新指向pHead，!=fast所以可以先判断
            slow = slow.next;
            fast = fast.next;
            count ++;
        }
        System.out.println(count);
        //计算环的节点数
        int loopCount = 0;
        do {
            fast = fast.next;
            loopCount ++;
        }while(slow != fast);
        System.out.println(loopCount);
        return slow;
    }
}