51Testing软件测试论坛

 找回密码
 (注-册)加入51Testing

QQ登录

只需一步,快速开始

微信登录,快人一步

查看: 1419|回复: 5

关于 “怎样才能检测到链表中存在循环” (某人说微软面试题目)

[复制链接]

该用户从未签到

发表于 2006-11-3 22:08:56 | 显示全部楼层 |阅读模式
面试题目是否要表达的是这个意思: 有一个单链表可能包含有循环,可能没有循环,怎么样设计一个算法判断它是否有循环。


设两个指针,一个步长为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;
回复

使用道具 举报

该用户从未签到

发表于 2006-11-4 08:16:40 | 显示全部楼层
思路真是好啊!
回复 支持 反对

使用道具 举报

该用户从未签到

发表于 2006-11-4 22:51:23 | 显示全部楼层
说得有理,由于p1向后移1个元素,p2向后移2个元素,每次移动之后,p2就比p1相差远1个元素,到了最后,如果链表是循环的话,到了最后p2肯定能够从后面追上p1
回复 支持 反对

使用道具 举报

该用户从未签到

发表于 2006-11-7 21:13:42 | 显示全部楼层
P1完全可以不移动,只是移动P2,P2=P2->next,知道p1=p2停止也可以吧。
回复 支持 反对

使用道具 举报

该用户从未签到

发表于 2006-11-8 19:56:01 | 显示全部楼层
原帖由 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:22 | 显示全部楼层
首先不得不说:老朴强啊!!!!!!!!!!
我当时咋就没想到这个方法呢?

另外回答nishuangxiJaneGu 的话,如果链表中的循环节点是3000指向1000,你怎么确定P1在哪里?
不然老朴应该不会用这么复杂的指针
回复 支持 反对

使用道具 举报

本版积分规则

关闭

站长推荐上一条 /1 下一条

小黑屋|手机版|Archiver|51Testing软件测试网 ( 沪ICP备05003035号 关于我们

GMT+8, 2024-3-29 13:45 , Processed in 0.066894 second(s), 24 queries .

Powered by Discuz! X3.2

© 2001-2024 Comsenz Inc.

快速回复 返回顶部 返回列表