【 以下文字转载自 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 的大作中提到】 : 【 以下文字转载自 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就可以了。不允许修改,谁有好办法嘛?
c*t
14 楼
没帐号的话只能看几次
S*5
15 楼
class B. that's fine, don't worry.
n*t
16 楼
脖子上的袋子是什么东西?
A*h
17 楼
这个戏的节奏是很好的。深度是需要进度做代价的,否则就是浮光掠影而已。
f*e
18 楼
我貌似有发过中文短信 啥叫网络不支持中文啊?
【在 t******m 的大作中提到】 : sprint网络不支持中文
g*e
19 楼
贴一个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
o*y
20 楼
帐号是免费的,我刚刚注了一个
【在 c****t 的大作中提到】 : 没帐号的话只能看几次
m*h
21 楼
同意
【在 O*****x 的大作中提到】 : 很萌
g*y
22 楼
你确定对方受到的不是乱码?
【在 f****e 的大作中提到】 : 我貌似有发过中文短信 : 啥叫网络不支持中文啊?
g*s
23 楼
讲讲思路?
【在 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
s*0
24 楼
good !!!!
m*h
25 楼
同问,像是什么气囊
【在 n********t 的大作中提到】 : 脖子上的袋子是什么东西?
h*i
26 楼
短信设置成unicode就不会收到乱码了
【在 g*******y 的大作中提到】 : 你确定对方受到的不是乱码?
g*e
27 楼
有点类似binary search,每次把内外的距离缩短一半
【在 g*********s 的大作中提到】 : 讲讲思路?
o*y
28 楼
上面还有面试题...看见几个精算intern的面试题 1.How many taxis are there in New York City at any given point in time? 2.How much revenue has last week's football games generated? 有点BT啊...要是碰上了的话我估计就自己编出一堆assumption来然后根据这些自己定 的前提来估算了
*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
38 楼
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
39 楼
这个都不知道的话还玩啥?
【在 g*********s 的大作中提到】 : how u know they would meet again?
g*e
40 楼
高,收我为徒吧
【在 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
41 楼
要用同余,需要先证明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. : 用同余可以证明。