Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:

Can you solve it without using extra space?

这个需要传说中的定理：

慢指针从快指针和慢指针第一次相遇的位置开始移动，另一个指针从head开始移动，两者相遇的点即为环入口。

相关证明参考site：环的连接点

代码如下：

ListNode *detectCycle(ListNode *head) {
        ListNode *one = head, *second = head, *ptr = head;
        
        while( second && second->next )
        {
            one = one->next;
            second = second->next->next;
            if( one == second )
            {
                while( one != ptr )
                {
                    one = one->next;
                    ptr = ptr->next;
                }
                return ptr;
            }
        }
        return NULL;
    }