51Testing软件测试论坛

标题: 关于 “怎样才能检测到链表中存在循环” （某人说微软面试题目） [打印本页]

作者: pcl2004_27 时间: 2006-11-3 22:08
标题: 关于 “怎样才能检测到链表中存在循环” （某人说微软面试题目）
面试题目是否要表达的是这个意思：有一个单链表可能包含有循环，可能没有循环，怎么样设计一个算法判断它是否有循环。

设两个指针，一个步长为1，一个步长为2，在单链表中向后移动，如果链表中有循环，则两个指针肯定会相遇
理由：假设3个元素的链表中第2个元素的后面是第1个元素。设置两个指针p1和p2，p1指向第1个元素，p2指向第3个元素，看看它们是否相等。如果相等就属于上述这种特殊情况。如果不等，把p1向后移一个元素，p2向后移两个元素。检查两个指针的值，如果相等，说明链表中存在循环。如果不相等，继续按照前述方法进行。如果出现某个指针是NULL的情况，说明链表中不存在循环。如果链表中存在循环，用这种方法肯定能够检测出来，因为在单链表的环中其中一个指针肯定能够追上另一个（两个指针具有相同的值）。

if (head==NULL) return true;

p=head; q=head->next;
while (q!=nil && q->next!=nil && p!=q){
p=p->next;
q=q->next->next;
}

if (p==q) return false;
else return true;

作者: wssgily 时间: 2006-11-4 08:16
思路真是好啊!

作者: zhou840401 时间: 2006-11-4 22:51
说得有理,由于p1向后移1个元素,p2向后移2个元素,每次移动之后,p2就比p1相差远1个元素,到了最后,如果链表是循环的话,到了最后p2肯定能够从后面追上p1

作者: nishuangxi 时间: 2006-11-7 21:13
P1完全可以不移动，只是移动P2，P2＝P2－>next，知道p1＝p2停止也可以吧。

作者: JaneGu 时间: 2006-11-8 19:56

原帖由 nishuangxi 于 2006-11-7 21:13 发表
P1完全可以不移动，只是移动P2，P2＝P2－>next，知道p1＝p2停止也可以吧。

我同意！P2＝P1或P2＝NULL就停止，P2＝P1为存在循环，P2＝NULL为不存在循环。

如果这个单链表存在n个元素，（n>=1）P2在P1之前一步，则需n-1次P2可追上P1（如果存在循环的话）。 P1不移动的话也一样需n-1次。

作者: 于淼 时间: 2006-11-13 14:37
首先不得不说：老朴强啊！！！！！！！！！！
我当时咋就没想到这个方法呢？

另外回答nishuangxi 和JaneGu 的话，如果链表中的循环节点是3000指向1000，你怎么确定P1在哪里？
不然老朴应该不会用这么复杂的指针

欢迎光临 51Testing软件测试论坛 (http://bbs.51testing.com/)