《剑指offer》链表中环的入口节点

题目

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

思路

1. 最容易想到的解法是利用HashSet。每访问一个节点，先判断HashSet中是否已经存入了当前节点，如果有说明这个节点就是环入口，如果没有就将当前节点存入HashSet。这个解法的时间复杂度是O(N),空间复杂度是O(N)。
2. 空间复杂度O(1)的解法。快慢指针法：维护两个指针，都从头节点出发，慢指针每次向后移动一个节点，快指针每次向后移动两个节点。如果有环，相遇后将其中一个节点指向头节点，然后两个节点每次都向后移动一个节点，再次相遇时的节点就是环入口。为了证明此解法的正确性，首先抛出两个结论：(1)快慢指针必相遇；(2)两个指针一个从头节点出发，一个从像雨点出发，再次相遇时必在环入口
3. 证明结论一：若有环，当慢节点进入环后，相当于快节点对慢节点的追及问题，由于快节点比慢节点每次多移动一个节点，所以快慢节点比相遇于环中某节点
4. 证明结论二：
   假设A为头节点，B为环入口，C为第一次相遇的点（相遇的必然性见结论一），AB=a,BC=b,CB=c.相遇时慢节点的路程为a+b，快节点的路成为a+b+(b+c)k，k>=1.
   可得(a+b)2=a+b+(b+c)k,k>=1.
   整理得a=(b+c)(k-1)+c,可见再次相遇时比相遇于点B

   public ListNode EntryNodeOfLoop(ListNode pHead)
        {
            if(pHead==null){
            return null ;
        }
        ListNode p1=pHead;
        ListNode p2=pHead;
        while(p1!=null&p2.next!=null){
            p1=p1.next;
            p2=p2.next.next;
            if(p1==p2){
                p1=pHead;
                while(p1!=p2){
                    p1=p1.next;
                    p2=p2.next;
                }
                return p1;
            }
        }
        return null;

        }