wljyy521 发表于 2012-6-4 22:16:48

一个简单的面试题关于单链表的

单链表中怎么判断有环？这里所说的有环不一定是单链表的尾部指向首部的，这样也行，看下图



大家看一看聊一聊

hslx111 发表于 2012-6-4 22:36:28

两个头指针p1,p2 p1一次走一个节点 p2一次走两个节点
如果:
1.p1或p2为null 返回 无环
2.p1==p2 返回 有环

wljyy521 发表于 2012-6-4 22:40:32

ls 说的不错:lol

fghhslk 发表于 2012-6-4 22:52:50

每个节点里设个访问标志（方法是不是比较2。。。{:6_206:}）

cq696925 发表于 2012-6-4 22:55:43

数据结构教材里有判断是否有环的详细说明

断崖之殇 发表于 2012-6-5 00:06:18

问一下，这个是在不知道长度的前提下么？

wljyy521 发表于 2012-6-5 00:06:54

断崖之殇 发表于 2012-6-5 00:06 static/image/common/back.gif
问一下，这个是在不知道长度的前提下么？

ens

断崖之殇 发表于 2012-6-5 00:50:19

确实有些意思，这里面还有一些推广，可以看看
http://www.cnblogs.com/zhyg6516/archive/2011/03/29/1998831.html

maxOrder石 发表于 2012-6-5 23:28:23

hslx111 发表于 2012-6-4 22:36 static/image/common/back.gif
两个头指针p1,p2 p1一次走一个节点 p2一次走两个节点
如果:
1.p1或p2为null 返回 无环


这个只能判断最小的环是吧

hslx111 发表于 2012-6-6 13:33:22

maxOrder石 发表于 2012-6-5 23:28 static/image/common/back.gif
这个只能判断最小的环是吧

你的意思是一个单链表里有多个环?
这个没啥意义吧,本来有环就不是单链表了.多个环就是图了啊

maxOrder石 发表于 2012-6-6 13:41:30

hslx111 发表于 2012-6-6 13:33 static/image/common/back.gif
你的意思是一个单链表里有多个环?
这个没啥意义吧,本来有环就不是单链表了.多个环就是图了啊

也是，楼主的说法让我糊涂了

sissi 发表于 2012-6-6 13:55:14

不是计算机专业的飘过看来我得补点常识了

fancyboy 发表于 2012-6-6 18:35:10

前些日子baid二面的题目

jianghaoran110 发表于 2012-6-6 19:45:06

怎么这里都有广告了

tpoisonooo 发表于 2012-6-21 22:15:39

本帖最后由 tpoisonooo 于 2012-6-21 22:20 编辑

逢贴必顶:P。
页: [1]
查看完整版本: 一个简单的面试题关于单链表的