如何才能检测到链表中存在循环呢?
如何才能检测到链表中存在循环呢?
对访问过的每个元素作个标记,遍历整个链表,当第一次遇到作过标记的元素,则找到了环的开始节点。 条件: 链表存在于只读存储区,不可做标记。 方法: 把已过的节点指针放入一个数组中,每次检查新的节点指针的时候,就在表中查找,看是否存在相同的节点。
如果存在,则表明该节点为环的开始节点。那么通常的做法可以使用哈希表和散列函数,来存放以检查过的节点和检查节点,重点需要优化的也是这个地方。 条件: 链表长度是任意的,而且循环也可能出现在任何地方。 方法: 首先,排除一种特殊的情况,就是3个元素的链表中第2个元素的后面是第1个元素。
设置两个指针p1和p2,p1指向第1个元素,p2指向第3个元素,看看它们是否相等。如果相等就属于上述这种特殊情况。如果不等,把p1向后移一个元素,p2向后移两个元素。检查两个指针的值,如果相等,说明链表中存在循环。如果不相等,继续按照前述方法进行。
如果出现某个指针是NULL的情况,说明链表中不存在循环。如果链表中存在循环,用这种方法肯定能够检测出来,因为在单链表的环中其中一个指针肯定能够追上另一个(两个指针具有相同的值)。不过该方法可能需要对链表遍历几次才能检测出来。
答:对访问过的每个元素作个标记,遍历整个链表,当第一次遇到作过标记的元素,则找到了环的开始节点。 条件: 链表存在于只读存储区,不可做标记。 方法: 把已检查过的节...详情>>