社区
C语言
帖子详情
汤姆逊的面试试题:怎么快速检测出一个巨大的链表中的死链?
zgy166
2004-09-06 09:53:36
怎么快速检测出一个巨大的链表中的死链?我实在没有想出好办法,只能说,没办法,只能一个一个的比了...各位高手有没有什么好办法?
...全文
6152
247
打赏
收藏
汤姆逊的面试试题:怎么快速检测出一个巨大的链表中的死链?
怎么快速检测出一个巨大的链表中的死链?我实在没有想出好办法,只能说,没办法,只能一个一个的比了...各位高手有没有什么好办法?
复制链接
扫一扫
分享
转发到动态
举报
写回复
配置赞助广告
用AI写文章
247 条
回复
切换为时间正序
请发表友善的回复…
发表回复
打赏红包
blackcrusoe
2004-10-19
打赏
举报
回复
这么热闹啊,我也来凑个兴。我的方法可以称为“回溯法”或“顺逆法”,思路是“以始为终”,虽然不知道有没有结尾,但它一定有开头,那么就把开头改成结尾,方法如下:
首先把头元素的next域置为null,然后对后面的指针依次反向,也就是指向前一个元素,那么最后必定会遇到null,这时判断:如果最后一个元素是头元素,那么就是有环的,否则就没有。
复杂度:应该在a*N到a*2N之间,但是a可能比较大。
缺点:只能检测是否有环,不能定位环
链表被破坏(没环时所有指针反向,有环时环的方向改变),需要再进行一次如上的过程才能恢复。
lwj_dxy
2004-10-18
打赏
举报
回复
mark
joinrry
2004-10-18
打赏
举报
回复
mark
stonepeter
2004-09-12
打赏
举报
回复
怎么用概率算法啊?原听其详!
庄鱼
2004-09-12
打赏
举报
回复
继续看帖,luclululu(噢哈)的方法在数学上就是老迈的方法,只是额外的增加一个记录入口的方法,但我以为完全没有必要,作为函数来说,函数的功能越简单,适用的范围就越广,没有必要将两者合在一起。因为有时我们仅仅想知道是否出现死链(带尾巴的环),以此判定数据有效性;当功能越多,为不必要的附加功能付出的系统代价就越多,不如拆成两个函数的好。
171558134
2004-09-12
打赏
举报
回复
我同意楼上的说法!计算概率后可以缩小问题面积,然后在用前面说的做示标,我想效率会快的多!
庄鱼
2004-09-12
打赏
举报
回复
从数学上讲,老迈这说的方法很适用于单指针结构情况,时间复杂度为2*N。
我在这里想问大家一个问题,对于多指针的树来说,如何避免出现指针的回绕(指向已用过的地址)?不知大家有无兴趣?
greendragon2008
2004-09-12
打赏
举报
回复
试着用 概率算法的思想 可能好一些
herryhuang
2004-09-12
打赏
举报
回复
Cybergate() :
你所有的问题,在前面已经有详尽的论述,请仔细看前面的帖子。
darcymei
2004-09-11
打赏
举报
回复
的确是..当时主要是要求几乎不需要辅助空间的情况下,对一个任意长不可修改链表进行是否有循环存在的检查。
Maxwell
2004-09-11
打赏
举报
回复
两个指针遍历,一个每次一步,一个每次两步,如果两个指针相等了就是有环的。
这好像是微软的一个面试题吧。
Cybergate
2004-09-11
打赏
举报
回复
呵呵,虽然绕了这么多弯子,不过真的很精妙啊
Cybergate
2004-09-11
打赏
举报
回复
问题三:
你说按照你的方法可以确定环的位置,什么叫做确定环的位置呢?是知道环中的一点吗?
如果这样的话,那个快慢追踪法也是可以的,因为最后重合的时候必定是在环中;
如果不是这样,也就是说要知道环的头了,但是你插入的节点很可能不是在环头啊,那你怎么追溯到环头的位置呢?
herryhuang
2004-09-11
打赏
举报
回复
Cybergate() :
我在后来已经改变了做法了,现在的方案是这样:
申请一块空间,其中有很多指针
void* p[MAX];
未插入时:
node1->next == node2
插入后:
node1->next == p[n];
*p[n] == node2
判断的时候只需要判断
p <= &p[n] <= &p[MAX];
Cybergate
2004-09-11
打赏
举报
回复
问题二:
---------------------------
2。我插入的是一个特殊的节点,甚至很可能数据的结构都与原来的不同,这样就很容易通过读取其中的数据来判断这样的节点是不是我插入的。
---------------------------
这个似乎不太可靠吧,有可能误将某些普通节点误判成你插入的节点
就按照原来的结构,例如它的数据域就是一个int,他可能是任何整数,理想地假设什么数字不会出现似乎不是太现实哦。
Cybergate
2004-09-11
打赏
举报
回复
herry:
我有一些疑问:
------------------------------
struct Node
{
int data;
Node* next;
}
我插入的节点
struct Mynode
{
int nouse;
Node* flag; //注意这个位置对应原来的next,我只需要在这里写入NULL,即可标记这个键点是我插入的,然后根据后面的next找到下一个节点。因为原有的节点中的next的值除了最后一个,其他的一定不是NULL。
Node* next;
}
判断时:
if(node->next == NULL)
node = (Mynode*)node->next;
------------------------------
既然你插入的结点都有node->next=NULL,那么你怎么获取下一个节点的地址呢?
用你的上面的那个条件语句好像不行哦,转换指针类型之后得出来的还是NULL。
设插入的节点是node,前继节点是prev_node,后继节点是succ_node
当然你在第一遍遍历的时候,可以根据node的前继节点prev_node来知道node的实际后继节点succ_node,但是这时候prev_node的next指针将要被修改成&node,也就是说succ_node的地址永久丢失了!那么第二遍遍历的时候你怎么还原这个链表呢?
darcymei
2004-09-11
打赏
举报
回复
to luclululu(噢哈):
的确慢指针被追上是一圈还没到,但是块指针可能已经是n圈。
你认为你的算法是最快的,不对吧
不过可以肯定的是 所用辅助空间肯定是最小的:)
9headsnake
2004-09-11
打赏
举报
回复
ding
vzxq
2004-09-10
打赏
举报
回复
study
永夜星空
2004-09-10
打赏
举报
回复
贴太多了,只看了一部分,也不知道各位前辈是否已写出了我的这个想法:
1 申请一个新节点,先不要插入链表。
2 遍立链表,把每个访问过的节点的 NEXT 变量先保存到一个新表中,然后让它指向那个新节点。
3 第一次发现有节点的NEXT指向新节点那么它的上个节点就有问题。
4 原表已破坏了,要求恢复就依照第2步中的新表恢复一下,没要求的话第2步都懒得保存NEXT 了。
加载更多回复(227)
怎么
快速
检测
出
一个
巨大的单
链
表
中
是否具备
死
链
及其位置?
汤姆逊
的
面试
试题
:怎么
快速
检测
出
一个
巨大的单
链
表
中
是否具备
死
链
及其位置?
先给
出
各种
链
表
的定义:
循环
链
表
(Circular Linked List)是另一种形式的
链
式存储结构。它的特点是表
中
最后
一个
结点的指针域指向头结点,整个
链
表
形成
一个
环。由此,从表
中
任一点
出
发均可找到表
中
其他结点。
单
链
表
是指表
中
的每个结点只包含
一个
指针域,除头结点外每个结点只有
一个
直接前驱,除最后
一个
结点外每个结点只有
一个
直接后继。
转:C/C++
面试
之算法系列--怎样
快速
检测
出
一个
巨大的单
链
表
中
是否具备
死
链
及其位置...
怎样
快速
检测
出
一个
巨大的单
链
表
中
是否具备
死
链
及其位置Sailor_foreversailing_9806@163.com转载请注明http://blog.csdn.net/sailor_8318/archive/2008/10/13/3066292.aspx
汤姆逊
的
面试
试题
:怎么
快速
检测
出
一个
巨大的单
链
表
中
是否具备
死
链
及其位置?先给
出
各种
链
表
的定义:循环
链
表
(Circular...
C/C++
面试
之算法系列--怎样
快速
检测
出
一个
巨大的单
链
表
中
是否具备
死
链
及其位置
怎样
快速
检测
出
一个
巨大的单
链
表
中
是否具备
死
链
及其位置 Sailor_forever sailing_9806@163.com 转载请注明http://blog.csdn.net/sailor_8318/archive/2008/10/13/3066292.aspx
汤姆逊
的
面试
试题
:怎么
快速
检测
出
一个
巨大的单
链
表
中
是否具备
死
链
及其位置? 先给
出
各种
怎样
快速
检测
出
一个
巨大的单
链
表
中
是否具备
死
链
及其位置
From: http://blog.csdn.net/sailor_8318/archive/2008/10/13/3066292.aspx
汤姆逊
的
面试
试题
:怎么
快速
检测
出
一个
巨大的单
链
表
中
是否具备
死
链
及其位置? 先给
出
各种
链
表
的定义: 循环
链
表
(Circular Linked List)是另一种形式的
链
式存储结构。它的特点是表
中
最后
一个
结点的指针域指向
C/C++
面试
题目集锦(zz)
C/C++
面试
题目集锦[搜自www.csdn.net]Irene @ 2004-10-27 13:55一、输入
一个
n ,然后在屏幕上打印
出
NxN 的矩阵! 例如,输入
一个
3,则 1 2 3 8 9 4 7 6 5 输入
一个
4,则 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7 参考答案:
C语言
69,336
社区成员
243,078
社区内容
发帖
与我相关
我的任务
C语言
C语言相关问题讨论
复制链接
扫一扫
分享
社区描述
C语言相关问题讨论
社区管理员
加入社区
获取链接或二维码
近7日
近30日
至今
加载中
查看更多榜单
社区公告
暂无公告
试试用AI创作助手写篇文章吧
+ 用AI写文章