算法思想： 先分析是否有環。為此我們建立兩個指針，從header一起向前跑，一個步長為1，一個步長為2，用while（直到步長2的跑到結尾）檢查兩個指針是否相等，直到找到為止。
static bool JudgeCircleExists(Link head){Link first = head; //1 step each timeLink second = head; //2 steps each timewhile (second.Next != null && second.Next.Next != null){second = second.Next.Next;first = first.Next;if (second == first)return true;}return false;}那又如何知道環的長度呢? 根據上面的算法，在返回true的地方，也就是2個指針相遇處，這個位置的節點P肯定位于環上。我們從這個節點開始先前走，轉了一圈肯定能回來：
static int GetCircleLength(Link point){int length = 1;Link curr = point;while (curr.Next != point){length++;curr = curr.Next;}return length;}繼續我們的討論，如何找到環的“起始”點呢? 延續上面的思路，我們仍然在返回true的地方P，計算一下從有環單鏈表的表頭head到P點的距離。
static int GetLengthFromHeadToPoint(Link head, Link point){int length = 1;Link curr = head;while (curr != point){length++;curr = curr.Next;}return length;}如果我們把環從P點“切開”（當然并不是真的切，那就破壞原來的數據結構了），那么問題就轉化為計算兩個相交“單鏈表”的交點。一個單鏈表是從P點出發，到達P（一個回圈），距離M；另一個單鏈表從有環單鏈表的表頭head出發，到達P，距離N。
PRivate static Link FindIntersect(Link head){Link p = null;//get the point in the circlebool result = JudgeCircleExists(head, ref p);if (!result) return null;Link curr1 = head.Next;Link curr2 = p.Next;//length from head to pint M = 1;while (curr1 != p){M++;curr1 = curr1.Next;}//circle lengthint N = 1;while (curr2 != p){N++;curr2 = curr2.Next;}//recover curr1 & curr2curr1 = head.Next;curr2 = p.Next;//make 2 links have the same distance to the intersectif (M > N){for (int i = 0; i < M – N; i++)curr1 = curr1.Next;}else if (M < N){for (int i = 0; i < N – M; i++)curr2 = curr2.Next;}//goto the intersectwhile (curr1 != p){if (curr1 == curr2){return curr1;}curr1 = curr1.Next;curr2 = curr2.Next;}return null;}新聞熱點
疑難解答
