分类： C/C++
2009-12-19 09:34:11
C程序员面试
(1)怎样才能检测到链表中存在循环
面试者可能如下作答
1.
对访问过的每个元素做个标记，继续遍历这个链表，如果遇到某个已经做过标记的元素，说明链表存在循环。
链表位于只读区域，无法在元素上做标记
2.
当访问每个元素时，把它存在一个数组里。检查每个后据元素，看看它是否已经存在 数组中。(哈哈，也许有些人继续想用散列表来优化数组的访问)
内存空间有限，无法创建一个足够长的数组。但是，可以假定如果链表中存在循环，那么它出现在前面的N个元素中
3.
设置一个指针，指向链表的头部。在接下去 对直到第N个元素的访问中，把N-1个元素依次同指向的元素进行比较。然后指针移向下一个元素，把同后面的N-2个元素进行比较。根据这个方法依次进行比较，如果出现比较相等的情况，就说明前N个元素中存在循环，否则如果所有N个元素两两之间进行比较都不相等，说明链表中不存在循环。
链表的长度是任意的，而且循环可能出现在任何位置。
4.参考答案
首先，排除一种情况：3个元素的链表 ，第2个元素的后面是第一个元素。
设置两个指针P1和P2,P1指向一个元素，P2指向第3个元素，看看它们是否相等。如果相等就属于上述这种特殊情况。
如果不等，把P1后移一个元素，P2后移两个元素。检查两个指针的值，如果相等，说明链表中存在循环。如果不相等，继续按照前述方法进行。如果出现两个指针都是NULL的情况，说明链表中不存在循环。
如果链表中存在循环，用这种方法一定能检查出来，因为其中一个指针肯定能追上另一个(两个指针具有相同的值)，尽管可能要对这个链表经过几次遍历才能检测出来。
(2)不同的增值语句有什么区别
|
