由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
Programming版 - [合集] 关于求解链表中环的起始位置问题
相关主题
[合集] 快慢指针找链表中的环,别的步长行么?[合集] dynamic memory 问题求解
[合集] C#里面的动态数组是怎样定义的?[合集] 微软另一道智力题,求救
C++(非VC++) 删除链表时如何对指针操作? 在线等回复!谢谢![合集] 微软的一道逻辑题
讨论 找单链表倒数m的节点 (转载)[合集] 请问是不是所有编程语言的函数调用,Matlab/C++/Java/Delph
单链表里找循环链的起点的解法质疑[合集] 给定一个最小堆,如何查找某数是否存在此堆中?
JHQ的一道指针题。[合集] c++一个问题
typedef const char *month Table[3][合集] 到底有没必要学习.NET
用C设计Stack的interface,要求支持各种数据类型。 (转载)[合集] C++如何产生很大范围的随机数?
相关话题的讨论汇总
话题: 位置话题: 指针话题: 起始话题: 链表话题: 求解
进入Programming版参与讨论
1 (共1页)
b***y
发帖数: 2799
1
☆─────────────────────────────────────☆
wmbyhh (wmbyhh) 于 (Fri Jul 18 22:00:22 2008) 提到:
一个链表中有环,如何求解这个环的起始位置。
网上已经有人给出答案,就是用2个指针,p=p->next, q=q->next->next,找到它们相
遇的位置,再求解这个环长度Y,从起点head到这个相遇位置长度L,
然后另2个指针,1个从head出发,1个从距离相遇位置Y-L%Y位置出发,直到这2个指针
相遇,此时就是环在链表中的起始地址。
现在我还是不懂得,这个L%Y是如何来的。
请指点一下。
☆─────────────────────────────────────☆
goodbug (好虫) 于 (Fri Jul 18 22:12:19 2008) 提到:
这么复杂干啥?先找出环,这标准的跳1跳2就可以弄出来,转一圈记录长度。
然后环上设一指针静止,另一指针从头上走,碰到为止,记录步数。
如此转一整圈,最小值就是起始位置。
时间复杂度都是O(N^2)

☆──────────────
1 (共1页)
进入Programming版参与讨论
相关主题
[合集] C++如何产生很大范围的随机数?单链表里找循环链的起点的解法质疑
[合集] 为什么下面代码总是调试通不过?JHQ的一道指针题。
[合集] 到底要学习Perl,还是Python?typedef const char *month Table[3]
[合集] 学了很久C/C++,就为什么总是学不深呢。用C设计Stack的interface,要求支持各种数据类型。 (转载)
[合集] 快慢指针找链表中的环,别的步长行么?[合集] dynamic memory 问题求解
[合集] C#里面的动态数组是怎样定义的?[合集] 微软另一道智力题,求救
C++(非VC++) 删除链表时如何对指针操作? 在线等回复!谢谢![合集] 微软的一道逻辑题
讨论 找单链表倒数m的节点 (转载)[合集] 请问是不是所有编程语言的函数调用,Matlab/C++/Java/Delph
相关话题的讨论汇总
话题: 位置话题: 指针话题: 起始话题: 链表话题: 求解