学步园

 给定一个有环的链表，写一个算法，找出环的起点。

例如：

输入：A->B->C->D->E->C[与前面的C是同一个节点]

输出：C

判断一个链表是否存在环有一个简单的方法，就是使用一个快指针、和一个慢指针，快指针每次走两步，慢指针每次走一步，则如果有环，它们最后必然会相遇的。本题的难点在于要找出环的起点。其实也不难，与判断是否有环类似，用两个步长分别为1和2的指针遍历链表，直到两者相遇，此时慢指针走过的长度就是环的长度。另外相遇后把其中指针重新设定为起始点，让两个指针以步长1再走一遍链表，相遇点就是环的起始点。

证明也很简单，证明如下：

我们注意到第一次相遇，假设快慢指针在M点第一次相遇。

慢指针走过的路程S1 = K + B

快指针走过的路程S2 = K + n * 环长 + B,  这个时候快指针可能已经走了n圈了。

由于快指针比慢指针快一倍，所以S1  = S2/2，==>  K== n*环长 - B。

现在让一个指针从起点开始，另一个指针从M点同时开始，由于上面的等式，==》两个指针最后会在环的起点处相遇。

LinkedListNode FindBeginning( LinkedListNode head)  
{  
    LinkedListNode n1 = head;  
    LinkedListNode n2 = head;  
  
    //find meeting point  
    while( n2.next != NULL )  
    {  
        n1 = n1.next;  
        n2 = n2.next.next;  
        if (n1 == n2)   
        {  
            break;  
        }  
    }  
  
    //error check--there is no meeting point  
    if (n2.next == null)   
    {  
        return null;  
    }  
  
    /*Move n1 to head, Keep n2 at meeting point*/  
  
    n1 = head;  
    while (n1 != n2)   
    {  
        n1 = n1.next;  
        n2 = n2.next;  
    }  
    //Now n2 points to the start of the loop  
    return n2;  
}