汤姆逊的面试试题:怎么快速检测出一个巨大的链表中的死链?

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)

69,336

社区成员

发帖
与我相关
我的任务
社区描述
C语言相关问题讨论
社区管理员
  • C语言
  • 花神庙码农
  • 架构师李肯
加入社区
  • 近7日
  • 近30日
  • 至今
社区公告
暂无公告

试试用AI创作助手写篇文章吧