判斷單鏈表是否有環？如何找到環的“起始”點？如何知道環的長度？

算法思想
先分析是否有環為此我們建立兩個指針從header一起向前跑一個步長為一個步長為用while（直到步長的跑到結尾）檢查兩個指針是否相等直到找到為止
static bool JudgeCircleExists(Link head)
{
Link first = head; // step each time
Link second = head; // steps each time
while (secondNext != null &#;&#; secondNextNext != null)
{
second = secondNextNext;
first = firstNext;
if (second == first)
return true;
}
return false;
}

那又如何知道環的長度呢？
根據上面的算法在返回true的地方也就是個指針相遇處這個位置的節點P肯定位於環上我們從這個節點開始先前走轉了一圈肯定能回來
static int GetCircleLength(Link point)
{
int length = ;
Link curr = point;
while (currNext != point)
{
length++;
curr = currNext;
}
return length;
}

繼續我們的討論如何找到環的起始點呢？
延續上面的思路我們仍然在返回true的地方P計算一下從有環單鏈表的表頭head到P點的距離
static int GetLengthFromHeadToPoint(Link head Link point)
{
int length = ;
Link curr = head;
while (curr != point)
{
length++;
curr = currNext;
}
return length;
}

如果我們把環從P點切開（當然並不是真的切那就破壞原來的數據結構了）那麼問題就轉化為計算兩個相交單鏈表的交點（第題）
一個單鏈表是從P點出發到達P（一個回圈）距離M另一個單鏈表從有環單鏈表的表頭head出發到達P距離N
我們可以參考第題的GetIntersect方法並稍作修改
private static Link FindIntersect(Link head)
{
Link p = null;
//get the point in the circle
bool result = JudgeCircleExists(head ref p);
if (!result) return null;
Link curr = headNext;
Link curr = pNext;
//length from head to p
int M = ;
while (curr != p)
{
M++;
curr = currNext;
}
//circle length
int N = ;
while (curr != p)
{
N++;
curr = currNext;
}
//recover curr &#; curr
curr = headNext;
curr = pNext;
//make links have the same distance to the intersect
if (M > N)
{
for (int i = ; i < M &#; N; i++)
curr = currNext;
}
else if (M < N)
{
for (int i = 0; i < N – M; i++)
curr2 = curr2.Next;
}
//goto the intersect
while (curr1 != p)
{
if (curr1 == curr2)
{
return curr1;
}
curr1 = curr1.Next;
curr2 = curr2.Next;
}
return null;
}

From:http://tw.wingwit.com/Article/program/sjjg/201405/30932.html