题目：

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?

分析：

检查链表是否有回路。如果有回路，则返回回路的起始节点；如果没有，则返回null。

基本思路还是使用Floyd判圈算法。指针hare每次向后移动2个节点，指针tortoise每次向后移动1个节点。如果hare最终指向尾节点则该链表无回路。否则，该链表有回路。（详见《LeetCode #141 Linked List Cycle》）

现在我们已经知道了链表有没有回路，但是如何在不使用额外空间并且不修改原链表的基础上获得回路的起始节点呢？这需要一些数学推导：

设链表起始节点为H，回路起始节点为S，两指针第一次相遇节点为M。
设回路的长度为c，S到M的距离为c1，M到S的距离为c2。
设H到S的距离为d。
设hare每次移动2，tortoise每次移动1。移动k次后两者相遇。不难发现，H到M的距离为k。

为了便于理解，请参考下图：

由已知条件，可得到下列等式：

hare和tortoise相遇时，hare套了tortoise若干圈。则有：

2k – k = nc = k，n为正整数。

从上图中定义的距离关系，可以得到

c = c1 + c2
k = d + c1

由以上格式变换可得： d = nc – c1 = c2 + (n-1)c

该式具有什么重要意义呢？假设2个指针分别从H和M出发，都是每次移动1的距离，他们会在哪里相遇？

一个指针从H出发移动d后到达M。另一指针移动 c2 + (n-1)c，(n-1)c意味着绕了n-1圈又回到M，实际上相当于走了c2的距离，到达M。我们发现，两指针必然在S相遇。

此时两指针相遇的节点即是回路的起始节点。

代码：

C