有時候我們需要測試一個單向鏈表是否存在環。最土鱉的方法就是改變鏈表的數據結構，給每個節點添加一個bool變量，在未測試時全部初始化為false，然後遍歷鏈表，每訪問一個節點，先測試其bool成員來確定這個節點是否被訪問過，如果為true，則表示訪問過，則有環，否則設置bool成員為true，表明訪問過，然後繼續測試。
如果不改變數據結構的話，我們有以下的解決方案：
1. 測試是否有環：
我們可以構建兩個迭代器來遍歷鏈表，一個每一次移動一個節點，另外一個每次移動兩個節點。如果這兩個一快一慢的土鱉迭代器相遇了，也就是說他們在某個時刻都到了同一個節點，那麼我們可以肯定有環存在。直觀的理解就是讓兩個土鱉一快一慢在400米環形跑道上各選一個位置，然後同時順時針做死了跑，那麼這兩個土鱉總能相遇,因為一個比另外一個快。
如果需要嚴謹的證明，我們可以這樣理解。假設在某個迭代時刻，兩個土鱉迭代器（以後簡稱土鱉）都進入了環，一個距環起始點為i，一個距環起始點為j。這個假設必然有成立的時候，因為跑著跑著他們總會進入環，而且一旦進入那就出不來了，只能做死了跑。然後假設又跑了一會兒，這兩個土鱉相遇了，一個土鱉跑了x步，一個跑了2x步。如果這個環總共長n,也就是說慢土鱉需要跑n步才能跑完一圈。然後我們可以得出i+x和j+2x對於n同余，也就是說i+x和j+2x除以n的余數是相同的，寫成同余等式就是(i+x)=j+2x(mod n) ，根據同余加減法性質，我們可以讓上面的式子減去x=x(mod m)，得到i=(j+x)(mod m)。因為x未知，所以上面的式子是個同余方程，i、j都是普通整數，很明顯這個方程是有解的。例如2=(1+x)(mod 5)的一個簡單解就是1。所以這兩個土鱉跑著跑著總會相遇。也就是說我們上面檢測環的算法可行，不會死循環。
2. 獲取環起始點：
基於問題1的分析，快土鱉和慢土鱉總會在某個節點相遇，假設這個點為cross。同事假設環起始點為start。一個顯然的事實是，當兩個土鱉相遇時，慢土鱉跑過的路徑是快土鱉的一半。這樣的話，在相遇前，當慢土鱉跑了一般的時候，快土鱉已經經過了相遇點（落腳或者跨越）。這樣的話當慢土鱉跑完後半段的時候，快土鱉從相遇點開始又跑了同樣的路程到達了相遇點，這個路程的長度等於慢土鱉總共跑的長度。現在牛逼的地方來了，如果慢土鱉從頭開始跑的時候，有另外一個慢土鱉從相遇點cross開始跑，那麼他們兩個也會在相遇點相遇，我們稱這兩個土鱉分別為A和B。土鱉B走的路程和快土鱉後半段時間走過的路程是完全一樣的，唯一的區別就是他慢一點而已。現在第二個牛逼的地方來了，因為慢土鱉A和B的速度是一樣的，那麼他們在相遇點之前的節奏也是一樣的，也就是說他們在相遇點值錢已經相遇了，而且一同樣的速度相伴走到了相遇點cross。他們從什麼時候相遇開始這段快樂的旅程呢，當然是環起始點start。我們可以讓慢土鱉A和B從相遇點倒退，這樣就能理解為什麼他們在start點相遇了。OK，現在我們有了解決方案，讓慢土鱉A從鏈表頭start開始跑，讓另外一個慢土鱉從相遇點cross開始跑，他們第一次的相遇點就是環起始點。
大功告成，標點符號（廢話）有點多，大家不要介意。
下面是C++代碼：
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 template<typename T>
5 struct Node
6 {
7 T value;
8 Node* next;
9 };
10
11 //Test if a linked list has circle
12 template<typename T>
13 bool hasLoop(Node<T>* linkedList, Node<T>** loopCross = NULL)
14 {
15 //empty linked list, no circle
16 if(linkedList == NULL || loopCross == NULL) return false;
17
18 Node<T>* slowWalker = linkedList;
19 Node<T>* quickWalker = linkedList;
20 while(quickWalker != NULL && quickWalker->next != NULL)
21 {
22 // move the walker
23 slowWalker = slowWalker->next; //one each step
24 quickWalker = quickWalker->next->next; //two each step
25 if(slowWalker == quickWalker)
26 {
27 //has circle
28 *loopCross = slowWalker;
29 return true;
30 }
31 }
32
33 return false;
34 }
35
36 //Get the loop start node
37 template<typename T>
38 Node<T>* getLoopStart(Node<T>* linkedList, Node<T>* loopCross)
39 {
40 Node<T>* startFromHead = linkedList;
41 Node<T>* startFromCross = loopCross;
42 // Move one pointer from head and move another from the cross node.
43 // They will meet each other at the loop start node.
44 while(startFromHead != startFromCross)
45 {
46 startFromHead = startFromHead->next;
47 startFromCross = startFromCross->next;
48 }
49 return startFromHead;
50 }
51
52 int main()
53 {
54 Node<int>* linkedList = new Node<int>();
55 linkedList->value = 0;
56 linkedList->next = NULL;
57
58 Node<int>* pNode = linkedList;
59 Node<int>* crossNode = NULL;
60
61 for(int i = 1; i < 100; i++)
62 {
63 Node<int>* tem = new Node<int>();
64 tem->value = i;
65 tem->next = NULL;
66
67 pNode->next = tem;
68 pNode = tem;
69 // set the cross node;
70 if(i == 66)
71 crossNode = tem;
72 }
73
74 printf("test normal linked list:\n");
75 if(hasLoop(linkedList))
76 printf("has circle.\n");
77 else
78 printf("no circle.\n");
79
80 printf("test circle linked list:\n");
81 pNode->next = crossNode; // Create a circle
82
83 Node<int>* loopCross = NULL;
84 if(hasLoop(linkedList, &loopCross))
85 {
86 printf("has circle.\n");
87 Node<int>* loopStart = getLoopStart(linkedList, loopCross);
88 if(loopStart != NULL)
89 printf("the value of the circle start node is %d\n", loopStart->value);
90 }
91 else
92 printf("no circle.");
93 }
*
