找到单链表中环的入口

这是一个很经典的面试题目。

首先，我们要检测一个链表是否包含环。

典型的思路，快慢指针。快指针每次移动两个结点，慢指针移动一个结点。就像两辆车在环形跑道上比赛，速度差一倍，那么快的肯定会追上慢的（套圈）。

如果快的指针到头了，两者还是没有相遇，那么说明这个链表不包含环。

var slow = head;
var fast = head;

while (fast != null && fast.Next != null)
{
    slow = slow.Next;
    fast = fast.Next.Next;
    if (slow == fast)   // 相遇了
    {
        break;
    }
}

// 快的指针到头了，说明没有环，也就无所谓环的起始结点，所以返回 null
if (fast == null || fast.Next == null)
{
    return null;
}

我们需要知道，他们在哪里相遇了呢？

假设非环部分的长度是 $k$，那么，慢指针走了 $k$ 步，位于环的起始位置，快指针走了 $2k$ 步，除去非环部分的 $k$ 步，快指针在环里面走了 $k$ 步，考虑 $k$ 可能比环的长度大，我们可以认为，快指针从环起始位置往前走了 $M = k \% \text{LoopSize}$ 步，也就是说，快指针比慢指针快了 $M$ 步，从另一个角度看，快指针比慢指针慢了 $\text{LoopSize} - M$ 步。

之后，慢指针走 $\text{LoopSize} - M$ 步，快指针走 $2 \times (\text{LoopSize} - M)$ 步，两者相遇。相遇点距离环的起始位置距离是 $\text{LoopSize} - M$ （从环的起始结点向前走）。

找到了相遇位置，如何利用这个信息找到环的起始结点呢？

从相遇点再走多远能到环的起始点呢？$M$。

$M$ 和 $k$ 有什么关系呢？模。$k= M + N \times \text{LoopSize}$。那么，从另外一个角度看，从链表开始到环的开始之间是 $k$ 步；从相遇点继续向前，也是 $k$步就到了环的起始结点，无非是在环里面绕零圈，还是多绕几圈的区别。

知道了这个我们就可以解决这个问题了。当找到相遇点之后，把慢指针拿到链表开头，快指针不动，但是每次只移动一步，当两个指针再次相遇的时候，就到了环起始结点。

slow = head;
while (slow != fast)
{
    slow = slow.Next;
    fast = fast.Next;
}

return fast;