面试系列9--怎样才能检测到链表中存在循环
添加时间: 2007-4-8 4:29:07 作者: 微软认证参考 阅读次数:48 来源: http://www.d9soft.com
原题：
怎样才能检测到链表中存在循环 (from 《C专家编程》)
解答：
条件： 没有任何条件。
方法： 对访问过的每个元素作个标记，遍历整个链表，当第一次遇到作过标记的元素，则找到了环的开始节点。
条件： 链表存在于只读存储区，不可做标记。
方法： 把已 检查 过的节点指针放入一个数组中，每次检查新的节点指针的时候，就在表中查找，看是否存在相同的节点。如果存在，则表明该节点为环的开始节点。那么通常的做法可以使用哈希表和散列函数，来存放以检查过的节点和检查节点，重点需要优化的也是这个地方。
条件： 链表长度是任意的，而且循环也可能出现在任何地方。
方法： 首先，排除一种特殊的情况，就是3个元素的链表中第2个元素的后面是第1个元素。设置两个指针p1和p2，p1指向第1个元素，p2指向第3个元素，看看它们是否相等。如果相等就属于上述这种特殊情况。如果不等，把p1向后移一个元素，p2向后移两个元素。检查两个指针的值，如果相等，说明链表中存在循环。如果不相等，继续按照前述方法进行。如果出现某个指针是NULL的情况，说明链表中不存在循环。如果链表中存在循环，用这种方法肯定能够检测出来，因为在单链表的环中其中一个指针肯定能够追上另一个（两个指针具有相同的值）。
不过该方法可能需要对链表遍历几次才能检测出来。
上下文章:
上一篇文章: 【专题】VisualStudio2005（1） 下一篇文章: 程序员考试：证书样本