有时候我们需要测试一个单向链表是否存在环。最土鳖的方法就是改变链表的数据结构，给每个节点添加一个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: ");
　　75 if(hasLoop(linkedList))
　　76 printf("has circle. ");
　　77 else
　　78 printf("no circle. ");
　　79
　　80 printf("test circle linked list: ");
　　81 pNode->next = crossNode; // Create a circle
　　82
　　83 Node<int>* loopCross = NULL;
　　84 if(hasLoop(linkedList, &loopCross))
　　85 {
　　86 printf("has circle. ");
　　87 Node<int>* loopStart = getLoopStart(linkedList, loopCross);
　　88 if(loopStart != NULL)
　　89 printf("the value of the circle start node is %d ", loopStart->value);
　　90 }
　　91 else
　　92 printf("no circle.");
　　93 }