我同学最近面试某IT公司的电话面试一个题目，他说当时可能回答的不好，和我讨论了一下。这里来问问大家。
给你一个单向链表的头指针，可能最后不是NULL终止，而是循环链表。题目问你怎么找出这个链表循环部分的第一个节点。比如下面的链表：
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> (3) 循环
就应该返回结点3的位置。
当然尽量用少的空间和时间是题目的要求。
cjaizss 回复于：2007-02-05 14:17:57
两个指针，一个步长为1，一个步长为2，往前进，时间复杂度O(n),空间复杂度O(1)
converse 回复于：2007-02-05 14:23:17
引用：原帖由 cjaizss 于 2007-2-5 14:17 发表
两个指针，一个步长为1，一个步长为2，往前进，时间复杂度O(n),空间复杂度O(1)
这个题目和原来的判断链表是不是循环链表的问题有一些区别的,原来是要证明链表是不是循环的,现在的是已知某部分是循环的要求找到这个循环的头结点.
我想到的办法是,从头开始一次取出把链表中的结点组成另一个链表,判断这个链表是不是循环的,第一个满足条件的头结点就是了.
比如以上面的测试数据为例:
第一次取出:
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> (3)
第二次取出:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> (3)
第三次取出:
2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> (3)
以此类推.
不知道有没有更好的办法,关注.
boxpei 回复于：2007-02-05 14:30:56
所有节点排序，第一个重复出现的节点就是，抛砖引玉。
cjaizss 回复于：2007-02-05 14:34:43
引用：原帖由 converse 于 2007-2-5 14:23 发表
这个题目和原来的判断链表是不是循环链表的问题有一些区别的,原来是要证明链表是不是循环的,现在的是已知某部分是循环的要求找到这个循环的头结点.
我想到的办法是,从头开始一次取出把链表中的结点组成另一 ...
恩，刚才没细想，现在想想确实是那么回事情:)。
空间复杂度O(n),时间复杂度O(n^2)
构造一个长度为O(n)的buffer,折半查找插入排序
无论是空间复杂度，还是时间复杂度，这已经是极限。
级别无法提高，但是或许可以找到同一级别上更快的算法。
Edengundam 回复于：2007-02-05 14:38:48
引用：原帖由 converse 于 2007-2-5 14:23 发表
这个题目和原来的判断链表是不是循环链表的问题有一些区别的,原来是要证明链表是不是循环的,现在的是已知某部分是循环的要求找到这个循环的头结点.
我想到的办法是,从头开始一次取出把链表中的结点组成另一 ...
和我想得大致一样...但是复杂度O(n^2)
Edengundam 回复于：2007-02-05 14:41:34
引用：原帖由 boxpei 于 2007-2-5 14:30 发表
所有节点排序，第一个重复出现的节点就是，抛砖引玉。
这个应该是O(nlogn)了...主要开销是对指针地址排序...:em09:
这个我说错了...取所有节点地址的开销貌似..:em06:
[ 本帖最后由 Edengundam 于 2007-2-5 15:12 编辑 ]
bleem1998 回复于：2007-02-05 14:42:18
引用：原帖由 cjaizss 于 2007-2-5 14:17 发表
两个指针，一个步长为1，一个步长为2，往前进，时间复杂度O(n),空间复杂度O(1)
我的基于这个算法
首先确认是否存在循环
如果存在循环
那么最后两个指针相会的地方一定是在循环的圈圈里
如果对这个节点不断的做next的话
会出现死循环
OK
这个时候再从链表头头上开始
把每个节点都判断一下是否在那个循环的圈圈里
:)
这个算法不的内存消耗率为0
咩哈哈哈
lishengxu 回复于：2007-02-05 14:44:17
不太明白converse的算法，希望斑竹给解释一下呗~
你第一次取出了第一个节点，但是你只知道头节点，不知道尾节点和链表的长度啊？
你怎么能判断出什么时候第一次结束啊？
我觉得最好是能够给访问过的节点做上已经访问的标志，这样不就好办了么！
converse 回复于：2007-02-05 14:51:42
引用：原帖由 lishengxu 于 2007-2-5 14:44 发表
不太明白converse的算法，希望斑竹给解释一下呗~
你第一次取出了第一个节点，但是你只知道头节点，不知道尾节点和链表的长度啊？
你怎么能判断出什么时候第一次结束啊？
我觉得最好是能够给访问过的节点做上已 ...
是啊,不知道哪里结束是个问题,我马虎了.:oops:
1jjk 回复于：2007-02-05 14:55:34
我想
他的意思应该是
去掉非循环链表的节点，例如去掉节点到第8个时，正好形成了一个环，这个时候环的第一个节点算是8了，是了？
DraculaW 回复于：2007-02-05 14:59:21
设个一样长的hash 以地址为index 是否访问为key
当第一个index的key是被设置了的 那么就是 要找的那个了
呵呵
这个应该时间是o(n) 空间应该是o(n)吧 看hash值的选择了
converse 回复于：2007-02-05 14:59:22
引用：原帖由 1jjk 于 2007-2-5 14:55 发表
我想
他的意思应该是
去掉非循环链表的节点，例如去掉节点到第8个时，正好形成了一个环，这个时候环的第一个节点算是8了，是了？
最初是这个想法,但是前面的朋友已经说了不知道链表在哪里结束,是个麻烦的事情唉~~:shock::shock:
cjaizss 回复于：2007-02-05 15:04:14
平均
空间复杂度O(n),时间复杂度O(n^2)，这是不可超越的。
只可以在这一级别上提高。
1jjk 回复于：2007-02-05 15:07:38
引用：原帖由 converse 于 2007-2-5 14:59 发表
最初是这个想法,但是前面的朋友已经说了不知道链表在哪里结束,是个麻烦的事情唉~~:shock::shock:
是的
不能结束
可以用链表里面的data域判断吗？
例如第一个节点的data域为1，递加，然后到环的时候，环肯定得有第一个域和最后一个域相接啊
不过这样的话就要多申请点空间了
emacsnw 回复于：2007-02-05 15:07:56
引用：原帖由 cjaizss 于 2007-2-4 23:04 发表
平均
空间复杂度O(n),时间复杂度O(n^2)，这是不可超越的。
只可以在这一级别上提高。
为什么是这个结论？呵呵。
lishengxu 回复于：2007-02-05 15:21:09
这句话什么意思
我没看懂
第一个节点的data域为1，递加，然后到环的时候，环肯定得有第一个域和最后一个域相接啊
1jjk能解释一下么？
cjaizss 回复于：2007-02-05 15:28:30
引用：原帖由 emacsnw 于 2007-2-5 15:07 发表
为什么是这个结论？呵呵。
可以证明的。
这是对于链表元素个数事先不可知而言的。
如果事先链表元素个数大致知道，则存在
空间复杂度O(n),时间复杂度O(n)
1jjk 回复于：2007-02-05 15:36:08
引用：原帖由 lishengxu 于 2007-2-5 15:21 发表
这句话什么意思
我没看懂
第一个节点的data域为1，递加，然后到环的时候，环肯定得有第一个域和最后一个域相接啊
1jjk能解释一下么？
struct pointer{
int data;
struct pointer * next;
}
每个节点多一个int data;
当读一个next的时候data加一，然后这个data与下一个的data进行比较
也不知道这么做可以不可以
我的思路是这样的，电脑挂了，要不就在家好好的实验一下，呵呵
现在在网吧呢
langue 回复于：2007-02-05 15:39:16
--
大家讨论的气氛很好，继续…… :lol
--
lishengxu 回复于：2007-02-05 15:40:29
晕了，那不是把链表结构都给改了么？？
1jjk 回复于：2007-02-05 15:42:22
有改吗？
多了个域
langue 回复于：2007-02-05 15:44:15
引用：原帖由 lishengxu 于 2007-2-5 15:40 发表
晕了，那不是把链表结构都给改了么？？
引用：原帖由 1jjk 于 2007-2-5 15:42 发表
有改吗？
多了个域
链表是一种数据结构，而数据结构是用来承载数据的。这里的 data 就是一个数据域 :)
--
emacsnw 回复于：2007-02-05 15:49:07
引用：原帖由 1jjk 于 2007-2-4 23:42 发表
有改吗？
多了个域
我不认为可以这么做。假设公司仅仅要你效率高点的实现这么一个函数
struct Node *first_loop_node(struct Node *head);
你可以随便改变struct Node的定义吗？呵呵。
lishengxu 回复于：2007-02-05 15:50:40
我的意思是说节点那个结构体的结构不是改了么？
多了一个标志位对吧？若我不想改变原来节点的结构体呢？
1jjk 回复于：2007-02-05 15:51:19
引用：原帖由 emacsnw 于 2007-2-5 15:49 发表
我不认为可以这么做。假设公司仅仅要你效率高点的实现这么一个函数
struct Node *first_loop_node(struct Node *head);
你可以随便改变struct Node的定义吗？呵呵。
前辈批评得是啊
可以自己定义一个数据结构吗？
跟着这个数据结构同时执行操作；
不过空间是个问题啦！
诶~~！
emacsnw 回复于：2007-02-05 16:01:04
引用：原帖由 1jjk 于 2007-2-4 23:51 发表
前辈批评得是啊
可以自己定义一个数据结构吗？
跟着这个数据结构同时执行操作；
不过空间是个问题啦！
诶~~！
汗，千万别叫我“前辈”，搞的巨有压力-_-
这个题O(n)时间和O(n)空间的算法是很trivial的，只要把依次遍历，把地址存入hash就行了，第一次出现重复的地址就是需要的解。不过我在想是否有O(1)空间的算法，有点类似以前用两个额外指针来判断链表是否存在环的方法。
langue 回复于：2007-02-05 16:02:09
好，一个用内部方法，一个用外部方法。
1jjk 回复于：2007-02-05 16:05:12
引用：原帖由 emacsnw 于 2007-2-5 16:01 发表
汗，千万别叫我“前辈”，搞的巨有压力-_-
这个题O(n)时间和O(n)空间的算法是很trivial的，只要把依次遍历，把地址存入hash就行了，第一次出现重复的地址就是需要的解。
顶一下啊！
cjaizss 回复于：2007-02-05 16:07:38
引用：原帖由 emacsnw 于 2007-2-5 16:01 发表
汗，千万别叫我“前辈”，搞的巨有压力-_-
这个题O(n)时间和O(n)空间的算法是很trivial的，只要把依次遍历，把地址存入hash就行了，第一次出现重复的地址就是需要的解。不过我在想是否有O(1)空间的算法，有 ...
O(1)空间复杂度是不存在的，信息量不够。
emacsnw 回复于：2007-02-05 16:09:41
引用：原帖由 cjaizss 于 2007-2-5 00:07 发表
O(1)空间复杂度是不存在的，信息量不够。
刚开始我也这样想的，但是想到两个额外指针可以判断链表是否有循环，这里至少有些类似。
呵呵，当然是否存在这样的算法可能只有面试官知道了。
1jjk 回复于：2007-02-05 16:11:49
要不让那哥们找一下那个出题的哥们
然后给个答案，然后学习学习吧
boxpei 回复于：2007-02-05 16:14:22
hash本身的时间空间复杂度也要考虑吧。
cjaizss 回复于：2007-02-05 16:17:50
哦，存在空间复杂度O(1),时间复杂度O(n^2)的算法，利用原链表的存储空间。是种很朴素的算法，对于不可预知链表长度而言并不低效。
可预知长度的话，选择O(1)空间还要选择O(n)时间是不可行的。
bleem1998 回复于：2007-02-05 17:03:33
写了段python代码
验证了刚才的算法
没有复制任何数据
只是指针指来指去
#!/usr/bin/env python
nd7 = [1, None, 'nd7']
nd6 = [1, nd7, 'nd6']
nd5 = [1, nd6, 'nd5']
nd4 = [1, nd5, 'nd4']
nd3 = [1, nd4, 'nd3']
nd2 = [1, nd3, 'nd2']
head = nd1 = [1, nd2, 'nd1']
nd7[1] = nd3 #recycle
def get_next(node):
if node != None:
return node[1]
else:
return None
def has_cycle(head):
p1 = head
p2 = head
while (p1 != None) and (p2 != None):
p1 = get_next(p1)
p2 = get_next(p2)
p2 = get_next(p2)
if p1 == None or p2 == None:
return [0, None]
if id(p1) == id(p2):
return [1, p1]
return [0, None]
def node_in_cycle(node, cycle_nd):
bak = cycle_nd
while True:
if id(node) == id(cycle_nd):
return True
cycle_nd = get_next(cycle_nd)
if id(bak) == id(cycle_nd):
return False
def look_for_cycle_point(head, cycle_nd):
while head != None:
if node_in_cycle(head, cycle_nd):
return head
else:
head = get_next(head)
return None
if __name__ == '__main__':
print 'Go...'
ret = has_cycle(head)
if ret[0]:
node = look_for_cycle_point(head,ret[1])
print node[2]
else:
print 'No cycle'
skipjack 回复于：2007-02-05 17:10:26
时间复杂度O(n),空间复杂度O(n/8) ,引用计数大于1即是交结点。不知我这么说，多少人可以明白
[ 本帖最后由 skipjack 于 2007-2-5 17:12 编辑 ]
softsongs 回复于：2007-02-05 17:41:06
无知无谓啊～
引用：原帖由 cjaizss 于 2007-2-5 15:04 发表
平均
空间复杂度O(n),时间复杂度O(n^2)，这是不可超越的。
只可以在这一级别上提高。
softsongs 回复于：2007-02-05 17:44:30
做个标记，晚上听完音乐会回来解答，
基本上是把数组看成一颗树，对其进行深度遍历，刚开始每个节点mark为白色，遍历一次mark为灰色，回退过的几点编程白色。经历两次即为我们要找的节点。
cjaizss 回复于：2007-02-05 18:16:51
引用：原帖由 softsongs 于 2007-2-5 17:41 发表
无知无谓啊～
...
我的错。
在链表长度不可预知的情况下，也依然存在空间复杂度O(n),时间复杂度O(nlogn)的算法。
构造sort-tree存储信息。
时间复杂度算错了
独孤九贱 回复于：2007-02-05 19:31:59
觉得这题，就像字符串中查找子串……
win_hate 回复于：2007-02-05 19:43:26
设非循环部分有 a 个点， 循环部分有 b 个点
用大步小步法，小步步幅为 1， 大步步幅为 2，经过 i 步后重合。从重合点出发，搜索自身并记数，可以得到 b.
令 q = [(i-1)/b]
用两个指针，一个从 qb +1 点出发，一个从重合点出发，步幅为1，直到重合，经过的步数就是 r. 而 a=bq+r.
[ 本帖最后由 win_hate 于 2007-2-5 21:01 编辑 ]
azhoulinux 回复于：2007-02-05 20:18:18
是否可以这样考虑：
单链表每一个节点其指向下一个节点的指针都是不同的，这道题在于会出现
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> (3) 循环
2节点与8节点都是指向3节点，引入一个新的栈，存储每个节点指针的值，一旦出现相同的指针值，那么就可以说出现了循环，比如2节点与8节点都是指向3节点.
你们看看行不行？
Edengundam 回复于：2007-02-05 20:32:37
O(1)复杂度...意思是常量, 不随着实例规模的变化而变化. 一万个指针, 都应该记为O(1)...呵呵:em06:
O(n/8)应该表示为O(n)的复杂度...
zjw12112 回复于：2007-02-05 21:38:39
构造hash表，我觉得时间复杂度是0(nlog2^n)吧？不好意思，忘了hash的时间复杂度。
想出了一个空间复杂度为0(n),时间复杂度也为0(n)的算法，不知道是否可行，大家看一看。
首先根据链表创建一个逆序的链表。如下：
原始：1->2->3->4->5->6->7->8->(3)
逆序：1->2->3->8->7->6->5->4->(3)
赫赫，接下来就很容易判断了，分别从两个链表头指针开始，找到next指针不一样的那个节点就是最终目标了。
12013396 回复于：2007-02-05 21:53:46
引用：原帖由 cjaizss 于 2007-2-5 14:17 发表
两个指针，一个步长为1，一个步长为2，往前进，时间复杂度O(n),空间复杂度O(1)
标准答案!!
Edengundam 回复于：2007-02-05 22:24:48
引用：原帖由 cjaizss 于 2007-2-5 14:17 发表
两个指针，一个步长为1，一个步长为2，往前进，时间复杂度O(n),空间复杂度O(1)
恩...明白这个算法的意思...偶太弱了..这算法1967年就有了...:em06:
emacsnw 回复于：2007-02-06 04:27:23
想了一下，似乎下面的算法可以：O(1)空间，O(n)时间。
两个额外指针p1, p2，开始都指向头S。设需要找到的循环部分第一个结点的位置为A，S到A的距离为x (x可能为0），链表的循环部分长度为y (y > 0)。
算法开始和判断循环的方法一样：令p1每次走一步，p2每次走两步，我们知道，如果链表有环，最后p1和p2一定在环上某个地方B相遇，我们设A-B之间的距离为z (z可能为0)。
很显然，p1走了x+z步，那么p2走了2(x+z)步，由于p1和p2在这么多步后相遇，因此有2(x+z) - (x+z) = K*y (K > 0的整数)，因此我们有x+z = K*y。
假如我们能让p1在B点开始继续往前走x步的话，它一定会走到A，因为z+x是y的倍数。有人会说，费话如果知道x的话，我只要让p2从起点S开始往前走x步，不就也能走到A吗？其实解法就是这么简单，让p1在刚刚相遇的地方B继续一次走一步，而p2从起点S开始一次走一步，那么它们第一次相遇的地方一定是A，并且正好经过了x步（当然你不需要计数）。
这就是算法。还是比如下面的例子：0->1->2->3->4->5->6->7->8->(3)
刚开始p1, p2都在0，p1一次走一步，p2一次走两步，它们最终会在结点6相遇。这时候让p1继续从6开始往前走，而p2从0开始也一次往前走1步，那么我么就会发现它们会相遇在3，返回这个地址就是所需要的解。
lishengxu 回复于：2007-02-06 09:23:06
老兄你的算法不对阿2(x+z) - (x+z) = K*y
这等式有问题阿!!!!
因该是2(x+n*z)-(x+m*z) = k*y
[ 本帖最后由 lishengxu 于 2007-2-6 09:26 编辑 ]
emacsnw 回复于：2007-02-06 09:43:52
引用：原帖由 lishengxu 于 2007-2-5 17:23 发表
老兄你的算法不对阿2(x+z) - (x+z) = K*y
这等式有问题阿!!!!
因该是2(x+n*z)-(x+m*z) = k*y
p2比p1多走了环长的整数倍，有什么问题吗？
skipjack 回复于：2007-02-06 09:50:57
引用：原帖由 Edengundam 于 2007-2-5 20:32 发表
O(1)复杂度...意思是常量, 不随着实例规模的变化而变化. 一万个指针, 都应该记为O(1)...呵呵:em06:
O(n/8)应该表示为O(n)的复杂度...
哦～，我是想用O(n/8)强调空间复杂度为O(0)（可能就是你们常说的O(1)吧，没系统学习过算法，不会专业表达，但我感觉这题也不需要什么算法），gcc结构体4字节对齐时剩下的空间，以及结构体成员变量只要能挤出1个bit用于计数，就足够了。比什么大步、小步、二叉、折半，效率高多了。
Edengundam 回复于：2007-02-06 10:08:04
引用：原帖由 skipjack 于 2007-2-6 09:50 发表
哦～，我是想用O(n/8)强调空间复杂度为O(0)（可能就是你们常说的O(1)吧，没系统学习过算法，不会专业表达，但我感觉这题也不需要什么算法），gcc结构体4字节对齐时剩下的空间，以及结构体成员变量只要能挤出1 ...
给算法看看吧
你如何管理引用计数??你利用mark的办法吧??
你如何遍历一个可能有环的循环链表, 这样的遍历开销...
O(n/8)就是O(n)意思是: 复杂度和实例规模成线性关系.
skipjack 回复于：2007-02-06 10:36:21
引用：原帖由 Edengundam 于 2007-2-6 10:08 发表
给算法看看吧
你如何管理引用计数??你利用mark的办法吧??
你如何遍历一个可能有环的循环链表, 这样的遍历开销...
O(n/8)就是O(n)意思是: 复杂度和实例规模成线性关系.
夸张点～，这题有点像周易里的“悬魂梯”。中国自古推崇易数，早在西周时期，那个最流行推卦演数的时代，统治阶级完全控制掌握着这些秘密，不知比1967年早了多少年:)。如果找不到“悬魂梯”的结点，就别想从“悬魂梯”上下来。用在古墓里可以防盗哦。
找到你认为需要开销的空间：
1)一个结构体的大小如果是30字节，则在gcc优化的时候一定会扩展为32字节，4字节对齐可以提高访问速度。这两个字节不用白不用，为什么要浪费？当然这个结构体本身就是4字节对齐的，那我还有下面的方式2
2)如果链表中的结构体想在SMP中使用，就必须含有count、use、ref、flag等成员变量用于并行计算，我们大可以使用flag中的某一bit，用于mark。如果你的程序只用在UP环境下，并且不并行....那你自己想办法吧。
算法很简单，每从一个next遍历到下一个结点时，把结点内的mark位由0置为1，当你遍历到8结点返回3结点时，3结点的mark位为1,说明这个3号点是个交点。大步、小步好像需要遍历二次链表，我只需要遍历一次就ok了。
另外test_bit()、clear_bit()、set_bit()，这类函数用汇编很好实现的，效率很高。
Edengundam 回复于：2007-02-06 10:46:10
引用：原帖由 skipjack 于 2007-2-6 10:36 发表
夸张点～，这题有点像周易里的“悬魂梯”。中国自古推崇易数，早在西周时期，那个最流行推卦演数的时代，统治阶级完全控制掌握着这些秘密，不知比1967年早了多少年:)。如果找不到“悬魂梯”的结点，就别想从“ ...
首先我们不能假设有空闲bit. 因为总有时候结构体是刚好对齐的.
其次, 如果你每次都需要设置一次, 那么你检查完需要一次清0吧??
Finding a Loop in a Singly Linked List 讨论过这个算法.
The problem with this solution is ensuring that "bit" is marked as zero for all
the nodes before you start. If the linked list has a loop, it isn't possible to
iterate over each node to set "1" to "0" as an initial value for each node.
Even if you are able to solve the initial value problem, each node in a linked
list may not have a field to use for this purpose. Requiring such a field in
each node would mean that this is not a generic solution. As we will see
later, this field in not needed for a perfectly correct and efficient solution
anyway.
[ 本帖最后由 Edengundam 于 2007-2-6 10:48 编辑 ]
1jjk 回复于：2007-02-06 10:56:39
引用：原帖由 emacsnw 于 2007-2-6 04:27 发表
想了一下，似乎下面的算法可以：O(1)空间，O(n)时间。
两个额外指针p1, p2，开始都指向头S。设需要找到的循环部分第一个结点的位置为A，S到A的距离为x (x可能为0），链表的循环部分长度为y (y > 0)。
算法 ...
带环链：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 10
步长2：1 3 5 7 9 11 13 15 10 12 14 16 11 13 15 10 12 14 16 11 13 15 10 12 14 16 11 13 15 10 12 14 16 11 13 15 10 12 14 16 11 13 15 10 12 14 16 11 13 15 10 12 14 16 11 13 15 10
步长1：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 10 11 12 13 14 15 16 10 11 12 13 14 15 16 10 11 12 13 14 15 16 10 11 12 13 14 15 16 10 11 12 13 14 15 16 10 11 12 13 14 15 16
是这样的吗？
在15相遇
skipjack 回复于：2007-02-06 11:04:43
引用：原帖由 Edengundam 于 2007-2-6 10:46 发表
首先我们不能假设有空闲bit. 因为总有时候结构体是刚好对齐的.
其次, 如果你每次都需要设置一次, 那么你检查完需要一次清0吧??
Finding a Loop in a Singly Linked List 讨论过这个算法.
The ...
你说的清0是为了第二次遍历吧。
第一次遍历的时候我以bit为1说明为mark状态
第二次遍历的时候我以bit为0说明为mark状态
mark就是一个二值的翻板，并且当开始遍历的时候我知道翻板的当前状态。
至于你说的没有bit用于mark，这就是我一开始说的空间复杂度为O(n/8)的原因，如果有80000个结点，我需要10000个字节来mark。
Edengundam 回复于：2007-02-06 11:09:22
引用：原帖由 skipjack 于 2007-2-6 11:04 发表
你说的清0是为了第二次遍历吧。
第一次遍历的时候我以bit为1说明为mark状态
第二次遍历的时候我以bit为0说明为mark状态
mark就是一个二值的翻板，并且当开始遍历的时候我知道翻板的当前状态。
...
多出来的可以完全不用. 如果对于刚好对其的结构体. 这样开销在某些时候太大了. :em06:
这时候浪费就是一个对其长度.
这是非通用解:em06:
Edengundam 回复于：2007-02-06 11:19:58
再PS: 那篇文章应该是有些语境, 而非是一个完整的环境. 使用追赶法可以对现存的各种单链直接进行遍历. 二不需要对原始环境进行任何修改. 这里mark一定要从实践的起步开始全盘设计好. 不过讨论算法总是在一堆算法中找"最优解".
skipjack 回复于：2007-02-06 11:39:54
引用：原帖由 Edengundam 于 2007-2-6 11:19 发表
再PS: 那篇文章应该是有些语境, 而非是一个完整的环境. 使用追赶法可以对现存的各种单链直接进行遍历. 二不需要对原始环境进行任何修改. 这里mark一定要从实践的起步开始全盘设计好. 不过讨论算法总是在一堆算法中 ...
你说的追赶法最具通用性
我的mark法最具效率
对于复杂和大型的结构体，没有空闲位并且自身还是4字节对齐的情况太少了。
并且当我mark过一个结点后，如果在list_add（）函数中加一个判断，禁止mark后的结点加入链表，从本质上还可以避免这种回环的产生。
具体问题具体分析吧，对于面式的环境，我的回答最具杀伤效果。:em02:
BTW：从你的回复中也找到了我想法中的不足，谢谢。
Edengundam 回复于：2007-02-06 11:44:35
引用：原帖由 skipjack 于 2007-2-6 11:39 发表
你说的追赶法最具通用性
我的mark法最具效率
对于复杂和大型的结构体，没有空闲位并且自身还是4字节对齐的情况太少了。
并且当我mark过一个结点后，如果在list_add（）函数中加一个判断，禁止mark后的结 ...
我也长了很多见识, 把自己没有考虑的也顺便问了你. 呵呵, 同谢~~~
lovefreex 回复于：2007-02-06 12:30:29
引用：原帖由 converse 于 2007-2-5 14:23 发表
这个题目和原来的判断链表是不是循环链表的问题有一些区别的,原来是要证明链表是不是循环的,现在的是已知某部分是循环的要求找到这个循环的头结点.
我想到的办法是,从头开始一次取出把链表中的结点组成另一 ...
我觉得这个方法可行的(如果可以访问链表中的数据),可以依次取链表的前一部分(保存该部分的最后一个结点的指针域并将其赋值为null),判断后面一部分是否有循环,如果没有则指针域为空的那个结点为循环点,如果有,则恢复那个空指针,截取下一个结点
ArXoR 回复于：2007-02-06 14:38:49
引用：原帖由 emacsnw 于 2/6/07 04:27 发表
想了一下，似乎下面的算法可以：O(1)空间，O(n)时间。
两个额外指针p1, p2，开始都指向头S。设需要找到的循环部分第一个结点的位置为A，S到A的距离为x (x可能为0），链表的循环部分长度为y (y > 0)。
算法 ...
方法是对的, 问题有点点
z应该是p1从A到在B和p2相遇所走过的路程, 才能用那个方程
emacsnw 回复于：2007-02-06 16:30:14
引用：原帖由 ArXoR 于 2007-2-5 22:38 发表
方法是对的, 问题有点点
z应该是p1从A到在B和p2相遇所走过的路程, 才能用那个方程
p1应该是可以保证没有走完这个环的。
gaosen2463 回复于：2007-02-06 16:46:21
不能保证吧
如果环特别小呢
gaosen2463 回复于：2007-02-06 16:51:21
是我想错了
p1是不能走完哪个环
ArXoR 回复于：2007-02-06 19:08:49
引用：原帖由 emacsnw 于 2/6/07 16:30 发表
p1应该是可以保证没有走完这个环的。
是可以证明z<=y, 但是叙述上应该严谨... ^_^
sdbook 回复于：2007-02-08 17:34:04
算出循环链的长度，总长度－循环链长度。
tuzhiwei123 回复于：2007-02-09 08:50:02
访问的接点做个标记，如果发现在访问后面的节点出现标记，就知道从什么地方循环了
dixin01 回复于：2007-04-27 22:28:31
许多人犯了一个严重的错误，在不知道链表的确切个数的情况下，
是无法进行循环或递归的操作的，这样去求逆转链表或摘取节点，
会因为无法确定循环的结束条件，从而陷入死循环！
以下是我的解答：
struct node* find_cycleNode(struct node *list_x)
{
struct node *p0, *p1;
if (list_x==list_x->next)
return(list_x);
p1=list_x->next;
while (1) {
for(p0=list_x; p0!=p1; p0=p0->next)
if (p0==p1->next)
return(p0);
p1=p1->next;
}
}
算法的时间复杂度：O(n^2), 空间复杂度：O(1)
[ 本帖最后由 dixin01 于 2007-4-28 00:11 编辑 ]
emacsnw 回复于：2007-04-28 02:24:18
引用：原帖由 dixin01 于 2007-4-27 06:28 发表
许多人犯了一个严重的错误，在不知道链表的确切个数的情况下，
是无法进行循环或递归的操作的，这样去求逆转链表或摘取节点，
会因为无法确定循环的结束条件，从而陷入死循环！
以下是我的解答：
struct ...
两个步进不一样(1和2)的指针相等了就中止，怎么会死循环。
dixin01 回复于：2007-04-28 09:27:01
引用：原帖由 emacsnw 于 2007-4-28 02:24 发表
两个步进不一样(1和2)的指针相等了就中止，怎么会死循环。
你的算法是正确的，比我的效率高，时间复杂度为O(n)，我说的是其他人的。
星尘细雨 回复于：2007-04-28 10:05:59
两个步进不一样的指针是个好办法。
但如果有好的内存分配策略的话，应该可以简化这个问题。
比如说，链表的每一项，从前到后，分配的内存地址都是有序的的话，
只需要把list->next指针和list本身比较一下看是否符合顺序就知道是否找到节点了。
不过这个内存分配方法不好办。
deadlylight 回复于：2007-04-28 12:17:45
首先用1步长2步长的方法判断是否有环存在O(n)。
如果有环，那就再从头开始，看每个节点的next是不是空。如果是空，就是我们要找的节点；不是空的话，就把它置空。O(n)
以楼主的例子，到8的时候，前面的节点的next都是空了，然后8指向3，发现3的next为空，就找到了最终结果。
这样的方法复杂度时间O(n),空间O(1)
但是破环了原有的链表
如果想不破坏
就需要一个辅助链表保存原始链表的信息，这样就需要O(n)的空间
所以最终结论是时间空间都是O(n)
jist12321 回复于：2007-04-28 12:38:04
我想到一个新算法，不知道行不行得通，大家看一下，先是直接开一个空间，让这整个空间的地址是连续的，然后根据上面的连表一个个考过去，因为地址是连续的，所以当出现一个指向的结构体的地扯比自已小的时候，这时就出现了一个循环，也就是找到了楼主的循环点，可是这里有一个能点就是这个考的过程，我现在还没想出来．大家看看，能不能实现。
[ 本帖最后由 jist12321 于 2007-4-28 12:39 编辑 ]
deadlylight 回复于：2007-04-28 12:56:09
引用：原帖由 jist12321 于 2007-4-28 12:38 发表
我想到一个新算法，不知道行不行得通，大家看一下，先是直接开一个空间，让这整个空间的地址是连续的，然后根据上面的连表一个个考过去，因为地址是连续的，所以当出现一个指向的结构体的地扯比自已小的时候，这时 ...
为什么地址小的时候就可以断定是循环呢，这种说法没有任何根据
jist12321 回复于：2007-04-28 13:08:42
引用：原帖由 deadlylight 于 2007-4-28 12:56 发表
为什么地址小的时候就可以断定是循环呢，这种说法没有任何根据
对不起，后面没看下去，刚刚转回去看了一下，行不通。不过，一步二步法是绝对可以的，而且我认认应该是时间复杂度是最小的了。
jist12321 回复于：2007-04-28 13:24:12
引用：原帖由 星尘细雨 于 2007-4-28 10:05 发表
两个步进不一样的指针是个好办法。
但如果有好的内存分配策略的话，应该可以简化这个问题。
比如说，链表的每一项，从前到后，分配的内存地址都是有序的的话，
只需要把list->next指针和list本身比较一 ...
我想的方法跟你差不多啊，可是这个内存分配有序的话就不存在链表一说，直接用数组了，像我说用考出整个链表更可笑，链表尾都不知道，怎么可能知道考哪里为止。做了一回傻瓜。
zx_wing 回复于：2007-04-28 16:36:45
各位给了很多方法，可惜没给代码，小弟也就没认真看了。
长期做系统程序，算法思维僵化了，想从现在开始锻炼锻炼，我就直接贴代码了。
算法很笨，先用不同步长前进找到圈，然后把圈中所有元素存到数组中（c99动态数组），最后再从链表头走一遍，第一个在数组中存在的元素就是圈的首节点。
不会算复杂度，估计是O(n^3)左右了，:em15:太烂了，开始练习算法。
#include <stdio.h>
#include <stdlib.h>
typedef struct list
{
int val;
struct list *next;
} list_t;
//不用细看，用来产生带圈的链表。
//len参数指定链表长度，loop_pos指定最后一个元素指向链表中的第几个元素。
//loop_pos如果大于len,则链表尾指向链表头。
list_t *pro_list(int len, int loop_pos)
{
list_t *head = malloc(sizeof(list_t));
list_t *t = head, *n = head;
int i;
head->val = 0;
for ( i=1; i<len; i++ )
{
list_t *m = malloc(sizeof(list_t));
m->val = i;
t->next = m;
t = m;
}
if ( loop_pos <= len )
for ( i=0; i<loop_pos; i++ )
n = n->next;
t->next = n;
return head;
}
//链表打印函数，不用细看
void print_list(list_t *head)
{
list_t *t = head;
while (1)
{
printf("val:%d, addr:%p\n", t->val, t);
if ( NULL == t->next )
break;
t = t->next;
}
}
//用来找圈的头节点，被find_loop调用
//addr保存的是圈中所有节点的地址，head指向链表头，lo_len表示圈中有多少个节点
list_t *find_loop_begin(list_t *addr[], list_t *head, int lo_len)
{
int i;
list_t *t = head;
while (1)
{
for ( i=0; i<lo_len; i++ )
if ( addr == t )
return addr;
t = t->next;
}
// should not be here
return NULL;
}
list_t *find_loop(list_t *head)
{
list_t *t1 = head;
list_t *t2 = head->next;
while (1)
{
if ( t1 == t2 )
{
int lo_len = 1;
int i = 1;
t1 = t1->next;
//先找出圈中有多少个节点
while ( t1 != t2 )
{
lo_len ++;
t1 = t1->next;
}
//把圈中的所有几点存入数组
list_t *addr[lo_len];
addr[0] = t2;
t1 = t2->next;
while ( t1 != t2 )
{
addr[i++] = t1;
t1 = t1->next;
}
//找出圈中的第一个节点
return find_loop_begin(addr, head, lo_len);
}
t1 = t1->next;
t2 = t2->next->next;
}
return t1;
}
int main()
{
list_t *head = pro_list(20, 11);
list_t *lo = find_loop(head);
printf("val:%d, addr:%p\n", lo->val, lo);
//print_list(head);
}
星尘细雨 回复于：2007-04-28 17:01:51
怎么没有根据？
这个是有个前提条件的！只是满足这个前提条件比较困难而已。
thinkinnight 回复于：2007-04-28 20:07:02
引用：原帖由 deadlylight 于 2007-4-28 12:17 发表
首先用1步长2步长的方法判断是否有环存在O(n)。
如果有环，那就再从头开始，看每个节点的next是不是空。如果是空，就是我们要找的节点；不是空的话，就把它置空。O(n)
以楼主的例子，到8的时候，前面的节点的ne ...
我觉得这个算法是可以的，还有那个大步小步的，应该也是可以的，不过对于推出的公式，还不能确定是否正确，因为大小步不一定是一圈，而是大步m圈，小步n圈之后才相遇的，想到这个就晕了，就搞不清公式是否正确，不过应该大小步是能解这个问题的。
再想想。。。
thinkinnight 回复于：2007-04-28 20:52:05
引用：原帖由 emacsnw 于 2007-2-6 04:27 发表
想了一下，似乎下面的算法可以：O(1)空间，O(n)时间。
两个额外指针p1, p2，开始都指向头S。设需要找到的循环部分第一个结点的位置为A，S到A的距离为x (x可能为0），链表的循环部分长度为y (y > 0)。
算法 ...
这个算法应该是看懂了，画了个图分析了一下，似乎是这样的，如果还是有什么地方不对，请指出来。还是很有意思的一道题目。
softsongs 回复于：2007-04-28 22:16:22
把链表看成一个有向图，深度优先遍历该有向图，判断有无循环出现。
懒得再用中文写一遍具体算法了，看下面的代码实现吧，英文注释解释的很清楚了。
时间复杂度 O(e), 链表边的总数。
空间复杂度 O(1).
有向图采用邻接表实现。
/* file: DFSDetectLoop.cpp */
/*
* Detect if the graph has loop -- For both Undigraph and digraph
* Complexity: O(e); e is the number of arcs in Graph.
*
* BUG Reported:
* 1. Apr-26-07
* Not support Undigraph yet ! Fix me !!!
* - Fixed on Apr-26-08.
*
* Return
* 1 - Loop detected.
* 0 - No loop detected.
* *
* Algrithm:
* 1. Init all the nodes color to WHITE.
* 2. DFS graph
* For each the nodes v in graph, do step (1) and (2).
* (1) If v is WHITE, DFS from node v:
* (a) Mark v as GRAY.
* (b) For every nodes tv adjacent with node v,
* (i) If the current visiting node is gray, then loop detected. exit.
* (ii) Goto Step (1).
* (iii) All the nodes on sub-tree of tv have been visited. Mark node tv as BLACK.
* (2) All the nodes on sub-tree of v have been visited. Mark node v as BLACK.
*
* Function DFSDetectLoop is valid for both Undigraph and digraph.
*
* */
int DFSDetectLoop (ALGraph *graph, int VisitFunc (ALGraph *graph, int v))
{
int v;
for (v = 0; v < graph->vexnum; v++)
{
MarkNodeColor (graph, v, WHITE);
}
for (v = 0; v < graph->vexnum; v++)
{
if (graph->vertices[v].color == WHITE)
{
/* We are good to call DFSDetectLoopSub the first
* time with pv = -1, because no node equals -1.
* */
if (1 == DFSDetectLoopSub (graph, v, -1, VisitFunc))
return 1;
}
MarkNodeColor (graph, v, BLACK);
}
return 1;
}
/*
* Start from node v, DFS graph to detect loop.
* pv is the node that just visited v. pv is used to avoid v to visit pv again.
* pv is introduced to support Undigraph.
*
* NOTE:
* Before calling DFSDetectLoopSub, make sure node v is not visited yet.
* */
int DFSDetectLoopSub (ALGraph *graph, int v, int pv, int VisitFunc (ALGraph *graph, int v))
{
assert (graph->vertices[v].color == WHITE);
MarkNodeColor (graph, v, GRAY);
VisitFunc (graph, v);
ArcNode *arc;
arc = graph->vertices[v].firstarc;
while (arc)
{
int tv = arc->adjvex;
/* For Undigraph, if tv equals pv, this arc should not be count.
* Because we have just visited from pv to v.
* Just go ahead to check next vertex connected with v.
* 1----2, after visit 1, we will visit 2, while visiting 2, 1 will be the 1st node visited.
*
* For digraph, we need to check loop even tv equals pv.
* Because there is case that node v points to u, and u points to v.
* */
if ((graph->kind == AG) && (tv != pv))
{
if ( graph->vertices[tv].color == GRAY )
{
cout << "Gray node visited at node: " << tv + 1 <<endl;
cout << "DFSDetectLoopSub: Loop Detected at from node " << v + 1<<" to "<< tv + 1 <<" !" <<endl;
return 1;
}
if (graph->vertices[tv].color == WHITE)
{
if (1 == DFSDetectLoopSub (graph, tv, v, VisitFunc))
{
return 1;
}
}
/* At this line:
* (1)If tv's color is already BLACK; Go ahead checking next arc;
* (2)If the sub-tree of node tv has all been visited, mark as BLACK and check next arc;
* Backward tv to to v's other adjacent node. So tv should be marked as black.
* */
MarkNodeColor (graph, tv, BLACK);
}
arc = arc->nextarc;
}
return 0;
}
deadlylight 回复于：2007-04-29 18:50:15
80楼的方法肯定是错的
a+y*b和a+p*b理论上可以相等
但是不要忘了，这个时候你的两个指针步长都是1，速度相同，永远都追不上的
thinkinnight 回复于：2007-04-29 20:55:42
引用：原帖由 deadlylight 于 2007-4-29 18:50 发表
80楼的方法肯定是错的
a+y*b和a+p*b理论上可以相等
但是不要忘了，这个时候你的两个指针步长都是1，速度相同，永远都追不上的
:em06::em06::em06: 多谢指点
想了一下，的确是这里条件不够，有可能出现出现始终两个指针差n*b(n>0)圈的情况（并没有去找一个特殊的例子，但是我想了一下，这个情况应该是可能出现的），这样就会产生永远追不上的情况，那是否可以设置一个条件，记录下第一次相遇的那个节点，如果指针1又一次到达这个节点的时候，指针1暂时停止前进，而指针2向前b个节点呢？
win_hate 回复于：2007-04-30 09:51:06
这个帖子这么长了。看了后面的回复，觉得很多朋友没有理解 Emacsnw 的方法。其实他的方法已经很简明了，相比之下我给出的解答则比较艰涩隐晦。现在把我的方法解释一次，顺带也把 emacsnw 的方法说一下。
1、我的想法
[attach]192320[/attach]
设这些点的下标为 0, 1, 2, ...
看上面的图，红点是大步-小步法找到的。设起点到红点的长度为 i，环的长度为 b，则
从红点出发，每 b 步后，都回到红点。如果我们让指针从红点出发，回退 b 步，得到的点标记为黄色。此时，从红点或黄点出发，b 步后都落在红点上。容易看出，用两个指针，分别从红，黄两点出发，步幅为 1，则它们的首个重合点就是环首。
回退 b 步得到的点在实现上可以通过从起点走 i-b 步得到。 由于 2i>=i+b, i-b 总是合法的。
我在前面帖子给出的方法与这个是一样的，只是陈述方式不同，而且前面的帖子符号有点混淆。
另外 i=0 (mod b) 总是成立的，因为 i = 2i (mod b)。 所以我们有 b|i
2、对 Emacsnw 的方法的解释
用两个指针一个指向第 i 点，另一个指向第 2i 点，而它们都指向红点。现在它们都回退 i 步(步幅 1)，则一个指针退到起点0，另一个指针退到 i 点。 此时让两个指针按步幅1 向前走直到相交就是环首。
设置退到 0 点的指针叫 p，停留在 i 点的叫 q， 则 q 每走 b 步都留在红点，所以我们可以把 p 的起点提前 b 的一个倍数而不影响结果。这就是我在前面帖子中的做法，用 i 去除以 b.
[ 本帖最后由 win_hate 于 2007-4-30 10:12 编辑 ]
softsongs 回复于：2007-04-30 10:16:30
你这个图画的还有才了，呵呵。
引用：原帖由 win_hate 于 2007-4-30 09:51 发表
这个帖子这么长了。看了后面的回复，觉得很多朋友没有理解 Emacsnw 的方法。其实他的方法已经很简明了，相比之下我给出的解答则比较艰涩隐晦。现在把我的方法解释一次，顺带也把 emacsnw 的方法说一下。
1、 ...
shaohui 回复于：2007-04-30 12:52:48
win_hate,Emacsnw 的连个方法我觉得是一样的。应该是最好的解法了.时间是O(n),空间(1)
thinkinnight 回复于：2007-04-30 15:40:42
引用：原帖由 win_hate 于 2007-4-30 09:51 发表
这个帖子这么长了。看了后面的回复，觉得很多朋友没有理解 Emacsnw 的方法。其实他的方法已经很简明了，相比之下我给出的解答则比较艰涩隐晦。现在把我的方法解释一次，顺带也把 emacsnw 的方法说一下。
1、 ...
学习了，是我没有理解清楚。
:em06::em06:
:oops::oops:
GKL 回复于：2007-05-01 12:20:21
引用：原帖由 DraculaW 于 2007-2-5 14:59 发表
设个一样长的hash 以地址为index 是否访问为key
当第一个index的key是被设置了的 那么就是 要找的那个了
呵呵
这个应该时间是o(n) 空间应该是o(n)吧 看hash值的选择了
hash的话空间虽然是O(n)，但是实际上应该是k*n，k可能很大的哦
GKL 回复于：2007-05-01 12:22:55
引用：原帖由 cjaizss 于 2007-2-5 15:04 发表
平均
空间复杂度O(n),时间复杂度O(n^2)，这是不可超越的。
只可以在这一级别上提高。
不对吧，boxpei的算法可以做到空间O(n)，时间O(nlogn)的啊。排序用二叉树的话
GKL 回复于：2007-05-01 12:57:39
Sorry，没看到上面的大哥们的帖子
emacsnw 回复于：2007-05-02 11:55:04
引用：原帖由 win_hate 于 2007-4-29 17:51 发表
这个帖子这么长了。看了后面的回复，觉得很多朋友没有理解 Emacsnw 的方法。其实他的方法已经很简明了，相比之下我给出的解答则比较艰涩隐晦。现在把我的方法解释一次，顺带也把 emacsnw 的方法说一下。
1、 ...
赞这个图。。:shock:
gta 回复于：2007-05-03 17:54:50
引用：原帖由 win_hate 于 2007-4-30 09:51 发表
这个帖子这么长了。看了后面的回复，觉得很多朋友没有理解 Emacsnw 的方法。其实他的方法已经很简明了，相比之下我给出的解答则比较艰涩隐晦。现在把我的方法解释一次，顺带也把 emacsnw 的方法说一下。
1、 ...
这个解法太巧妙了
shaohui 回复于：2007-05-08 10:27:03
来一个与众不同的，是在其它地方看到的。
原来链表
->->-> x -> ->
^ |
| <- <-
一边走，一边把链表反向
绕了一圈之后，最后会走回起点
同时链表呈
->->-> x <- <-
| |
| -> -> y
显然，过程中可以统计出链表走过的节点数 L，不是环的部分走了2遍，也包括进去了
然后从起点走L/2步，走到那个中间节点，就是y，也是一边走一边反向
然后就是
<-<-<- x <- <- y'
| |
| <- <- y
然后两个指针都从y和y'开始走，各走一步，交点就是x，环起点
至于要还原链表，从y'走向头，反向一次就好了
andyxie407 回复于：2007-05-08 10:45:12
占个坑，留着用
emacsnw 回复于：2007-05-08 11:37:34
引用：原帖由 shaohui 于 2007-5-7 18:27 发表
来一个与众不同的，是在其它地方看到的。
原来链表
->->-> x -> ->
^ |
| <- <-
一边走，一边把链表反向
绕了一圈之后，最后会走回起点
同时链表呈
->-& ...
这个是[font=黑体][color=Blue]单向[/font][/color]链表啊。
FireR2 回复于：2007-05-08 13:02:03
最近似乎 总能看到 类似的题目，晕，难道面试管都上ChinaUnix？
thinkinnight 回复于：2007-05-08 13:32:34
引用：原帖由 shaohui 于 2007-5-8 10:27 发表
来一个与众不同的，是在其它地方看到的。
原来链表
->->-> x -> ->
^ |
| <- <-
一边走，一边把链表反向
绕了一圈之后，最后会走回起点
同时链表呈
->-& ...
y和y' 不清楚说的是哪个点，一个是L/2的点，另一个呢？
shaohui 回复于：2007-05-08 17:25:34
引用：
这个是单向链表啊。
注意每次遍历都会反转的
thinkinnight 回复于：2007-05-09 09:18:03
链表反转的那个方法
b为奇数的时候是不是不行？
fertiland 回复于：2007-05-09 10:46:24
http://ostermiller.org/find_loop_singly_linked_list.html
yuephone 回复于：2007-05-09 10:50:52
可不可以用地址来判断呀!
取指针指向的地址来进行对比,我感觉挺直观的
Michaelgs 回复于：2007-05-09 12:02:56
时间复杂度O(n)，空间复杂度O(1)， 方法如下：
设环的长度为Y
用两个步长分别为1和2的指针前进，第一次相遇之后再前进，第二次相遇时停止。
记下从第一次相遇到第二次相遇，步长为1的指针走过的步数S，则S＝＝Y。环的长度就知道了
用两个指针，一个在链头，一个走到链头后第Y个位置上
判断两个指针是否相等，如果是就是环的起始位置了
否则两个指针各自前进一步，再判断
goldensunflower 回复于：2007-05-11 11:59:37
学习了
|
