面试题23：链表中环的入口节点

题目：如果一个链表中包含环，如何找出环的入口节点？
思路：设置两个指针P1和P2，P2比P1每次多走一步，这样最后碰撞的时候为k。此时再设置两个节点N1和N2，N1在碰撞处，N2在起点，同时移动，N1和N2会在环入口处碰撞。
解决方案：

public class Question23 {
    static class ListNode{
        int value;
        ListNode next;
        public ListNode(int value){
            this.value = value;
        }
    }
    private static ListNode meetNode(ListNode head){
        if (head == null) return null;

        ListNode slow = head.next;
        if (slow == null) return null;

        ListNode fast = slow.next;
        while (fast != null && slow != null){
            if (fast == slow){
                return fast;
            }
            slow = slow.next;
            fast = fast.next;
            if (fast != null){
                fast = fast.next;
            }
        }
        return null;
    }

    public static ListNode entryNodeOfLoop(ListNode head){
        ListNode meetingNode = meetNode(head);
        if (meetingNode == null) return null;

        int nodesInLoop = 1;
        ListNode node1 = meetingNode;
        while (node1.next != meetingNode){
            node1 = node1.next;
            ++nodesInLoop;
        }

        node1 = head;
        for (int i=0; i<nodesInLoop; i++){
            node1 = node1.next;
        }

        ListNode node2 = head;
        while (node1 != node2){
            node1 = node1.next;
            node2 = node2.next;
        }
        return node1;
    }

    public static void main(String[] args) {
        ListNode pHead = new ListNode(1);
        ListNode pAhead = new ListNode(3);
        ListNode pBhead = new ListNode(5);
        ListNode pChead = new ListNode(7);
        pHead.next = pAhead;
        pAhead.next = pBhead;
        pBhead.next = pChead;
        pChead.next = pAhead;
        System.out.println(entryNodeOfLoop(pHead).value);
    }
}