原题：
怎样才能检测到链表中存在循环 (from 《C专家编程》)
解答：
条件： 没有任何条件。
方法： 对访问过的每个元素作个标记，遍历整个链表，当第一次遇到作过标记的元素，则找到了环的开始节点。
条件： 链表存在于只读存储区，不可做标记。
方法： 把已检查过的节点指针放入一个数组中，每次检查新的节点指针的时候，就在表中查找，看是否存在相同的节点。如果存在，则表明该节点为环的开始节点。那么通常的做法可以使用哈希表和散列函数，来存放以检查过的节点和检查节点，重点需要优化的也是这个地方。
条件： 链表长度是任意的，而且循环也可能出现在任何地方。
方法： 首先，排除一种特殊的情况，就是3个元素的链表中第2个元素的后面是第1个元素。设置两个指针p1和p2，p1指向第1个元素，p2指向第3个元素，看看它们是否相等。如果相等就属于上述这种特殊情况。如果不等，把p1向后移一个元素，p2向后移两个元素。检查两个指针的值，如果相等，说明链表中存在循环。如果不相等，继续按照前述方法进行。如果出现某个指针是NULL的情况，说明链表中不存在循环。如果链表中存在循环，用这种方法肯定能够检测出来，因为在单链表的环中其中一个指针肯定能够追上另一个（两个指针具有相同的值）。
不过该方法可能需要对链表遍历几次才能检测出来。
[重要提醒]对本篇资料有疑问，请到论坛讨论，尽量使文章准确无误>>>
[版权声明]BSD爱好者乐园站内文章，如来源不是互联网，则均系原创或翻译之作，可随意转载，或以此为基础进行演译，但务必以链接形式注明原始出处和作者信息，否则属于侵权行为。另对本站转载他处文章，俱有说明，如有侵权请联系本人，本人将会在第一时间删除侵权文章。
TAG: 循环 链表