g**e
发帖数: 6127 | 1 【 以下文字转载自 InterviewHackers 俱乐部 】
发信人: gate (离开之后，再见以前), 信区: InterviewHackers
标 题: find start point of loop from linked list
发信站: BBS 未名空间站 (Thu Jan 20 22:33:20 2011, 美东)
单链表找loop大家都会了，但是找start point of loop，要求o(n) time, o(1) space
，不能修改链表，感觉就不是那么容易了。
如果允许修改，很容易，reverse就可以了。不允许修改，谁有好办法嘛？ |
N***m
发帖数: 4460 | 2 我都忘记了，c不允许list 索引by index？
space
【在 g**e 的大作中提到】
: 【 以下文字转载自 InterviewHackers 俱乐部 】
: 发信人: gate (离开之后，再见以前), 信区: InterviewHackers
: 标 题: find start point of loop from linked list
: 发信站: BBS 未名空间站 (Thu Jan 20 22:33:20 2011, 美东)
: 单链表找loop大家都会了，但是找start point of loop，要求o(n) time, o(1) space
: ，不能修改链表，感觉就不是那么容易了。
: 如果允许修改，很容易，reverse就可以了。不允许修改，谁有好办法嘛？
|
g**e
发帖数: 6127 | 3 贴一个google到的，看上去应该是o(n)
Let x = the head of the list
Let y = some point on the loop (e.g. the place we detected the loop)
findloophead(x,y){
pointers t, a=x, b=next(y), c=y
while (1) {
t=midpoint (a,c)
if find (b,t,c) // t is in loop
then c=t
else a=next(t) // t is out of loop. move a to t
t= midpoint (b,c)
if find (a,t,c)
then c=t
else b=next(t)
if (a==b) return a;
if (a==c) or (b==c) return c;
}}
midpoint (e,f):
returns the pointer to the middle element (round toward front of list) ---
we can implement this with a pointer+double speed pointer walk
find (e,f,g):
returns true if we encounter f in a walk from e to g, otherwise false.
【在 N***m 的大作中提到】
: 我都忘记了，c不允许list 索引by index？
:
: space
|
g*********s
发帖数: 1782 | 4 讲讲思路？
【在 g**e 的大作中提到】
: 贴一个google到的，看上去应该是o(n)
: Let x = the head of the list
: Let y = some point on the loop (e.g. the place we detected the loop)
: findloophead(x,y){
: pointers t, a=x, b=next(y), c=y
: while (1) {
: t=midpoint (a,c)
: if find (b,t,c) // t is in loop
: then c=t
: else a=next(t) // t is out of loop. move a to t
|
g**e
发帖数: 6127 | 5 有点类似binary search，每次把内外的距离缩短一半
【在 g*********s 的大作中提到】
: 讲讲思路？
|
z****e
发帖数: 2024 | |
g*********s
发帖数: 1782 | 7 详细点？
【在 z****e 的大作中提到】
: 这题用同余原理即可。
|
g**e
发帖数: 6127 | 8 co ask
【在 g*********s 的大作中提到】
: 详细点？
|
z****e
发帖数: 2024 | 9 *p1 step size 1, *p2 step size 2, to find node where the two meet.
then, set p1 to head, and drive p1 and p2 to move on 1 step each time
simultaneously.
when p1 meet p2 again, that's the starting point of the loop.
用同余可以证明。 |
g*********s
发帖数: 1782 | 10 how u know they would meet again?
【在 z****e 的大作中提到】
: *p1 step size 1, *p2 step size 2, to find node where the two meet.
: then, set p1 to head, and drive p1 and p2 to move on 1 step each time
: simultaneously.
: when p1 meet p2 again, that's the starting point of the loop.
: 用同余可以证明。
|
|
|
z****e
发帖数: 2024 | 11 这个都不知道的话还玩啥？
【在 g*********s 的大作中提到】
: how u know they would meet again?
|
g**e
发帖数: 6127 | 12 高，收我为徒吧
【在 z****e 的大作中提到】
: *p1 step size 1, *p2 step size 2, to find node where the two meet.
: then, set p1 to head, and drive p1 and p2 to move on 1 step each time
: simultaneously.
: when p1 meet p2 again, that's the starting point of the loop.
: 用同余可以证明。
|
P********e
发帖数: 2610 | 13 要用同余，需要先证明p2和p1在圈内行走的历程只差一圈。
【在 z****e 的大作中提到】
: *p1 step size 1, *p2 step size 2, to find node where the two meet.
: then, set p1 to head, and drive p1 and p2 to move on 1 step each time
: simultaneously.
: when p1 meet p2 again, that's the starting point of the loop.
: 用同余可以证明。
|
g**e
发帖数: 6127 | 14 一个走一步，另一个走两步，fast pointer赶上最多只需要n-1次. 所以一圈就够了
【在 P********e 的大作中提到】
: 要用同余，需要先证明p2和p1在圈内行走的历程只差一圈。
|
X****r
发帖数: 3557 | 15 Not necessarily one round. It could be multiple rounds.
(but still works nevertheless)
【在 P********e 的大作中提到】
: 要用同余，需要先证明p2和p1在圈内行走的历程只差一圈。
|
P********e
发帖数: 2610 | 16 这个需要证明吧
一个走一步，另一个走两步，fast pointer赶上最多只需要n-1次. 所以一圈就够了
【在 g**e 的大作中提到】
: 一个走一步，另一个走两步，fast pointer赶上最多只需要n-1次. 所以一圈就够了
|
P********e
发帖数: 2610 | 17 可以多圈吗？能给个例子吗
【在 X****r 的大作中提到】
: Not necessarily one round. It could be multiple rounds.
: (but still works nevertheless)
|
z****e
发帖数: 2024 | 18 我是绝对菜鸟，下家还没找到呢。
版上师傅们这么多，随便拜一个都比我强万倍。
【在 g**e 的大作中提到】
: 高，收我为徒吧
|
X****r
发帖数: 3557 | 19 0->1->2->3->4->5->6->7->8->9->8
【在 P********e 的大作中提到】
: 可以多圈吗？能给个例子吗
|
P********e
发帖数: 2610 | 20 谢谢，出来了
0->1->2->3->4->5->6->7->8->9->8
【在 X****r 的大作中提到】
: 0->1->2->3->4->5->6->7->8->9->8
|
|
|
g**e
发帖数: 6127 | 21 假设loop length = n，当slow和fast两pointer都进入loop的时候，它们之间最大的距
离是n-1，那么fast追上最多需要n-1 step，也就是slow pointer走一圈之内
【在 P********e 的大作中提到】
: 这个需要证明吧
:
: 一个走一步，另一个走两步，fast pointer赶上最多只需要n-1次. 所以一圈就够了
|
g*********s
发帖数: 1782 | 22 ok. i see what u mean now. but i still don't think it's correct.
i'll make a new post to discuss ur approach.
【在 z****e 的大作中提到】
: 这个都不知道的话还玩啥？
|
z***e
发帖数: 5393 | 23 这是数学题啊。
别考虑什么linked list，把图画出来先：
<--m-----> |
P********e
发帖数: 2610 | 24 赞详细，我当初把k和d代错了，所以推出一圈：）
【在 z***e 的大作中提到】
: 这是数学题啊。
: 别考虑什么linked list，把图画出来先：
: <--m----->
|
