Loop in single linked list

来源: 外-国人 于 2009-05-15 07:55:51 [] [旧帖] [给我悄悄话] 阅读数 : (316 bytes)
本帖于 2009-06-09 09:31:02 时间, 由普通用户 康MM 编辑

Wow, 几天不见，这里正热闹，看来还是Progromers比Mathematician多。怪不得康MM被气得离家出走了。:)
既然大家对Programing感兴趣，给大家做一个。不过，哪位想Progrom也可以。
Any language is ok.

(An interview question)
Given a single linked list with n items.
Find an O(n) algorithm to detect any loops.

所有跟帖： 

• 这题很经典 -endofsuburbia- ♂ 给 endofsuburbia 发送悄悄话 endofsuburbia 的博客首页 (32 bytes) () 05/15/2009 postreply 09:26:24

• 2X追就可了。。。 -haha2000- ♂ 给 haha2000 发送悄悄话 (0 bytes) () 05/15/2009 postreply 12:51:13

• 没错。设置两个pointers，一个追另一个。追上为有Loop。 -戏雨飞鹰- ♀ 给 戏雨飞鹰 发送悄悄话 戏雨飞鹰 的博客首页 (0 bytes) () 05/15/2009 postreply 14:46:34

• 回复：没错。设置两个pointers，一个追另一个。追上为有Loop。 -外-国人- ♂ 给 外-国人 发送悄悄话 (16 bytes) () 05/17/2009 postreply 11:03:27

• a similar but harder problem -dynamic- ♂ 给 dynamic 发送悄悄话 (122 bytes) () 05/18/2009 postreply 09:43:31

• sum mod n -haha2000- ♂ 给 haha2000 发送悄悄话 (0 bytes) () 05/18/2009 postreply 09:52:57

• I asked a similar question in an interview. -乱弹- ♂ 给 乱弹 发送悄悄话 乱弹 的博客首页 (162 bytes) () 05/18/2009 postreply 10:01:54

• you are definitely right... I need to fix it :) -dynamic- ♂ 给 dynamic 发送悄悄话 (0 bytes) () 05/18/2009 postreply 10:48:03

• fix of the problem -dynamic- ♂ 给 dynamic 发送悄悄话 (160 bytes) () 05/18/2009 postreply 10:51:26

• algorithmic complexity requirement? -haha2000- ♂ 给 haha2000 发送悄悄话 (103 bytes) () 05/18/2009 postreply 19:19:21

• can be done in linear time... -haha2000- ♂ 给 haha2000 发送悄悄话 (150 bytes) () 05/18/2009 postreply 19:42:41

• it takes a bit more than that -dynamic- ♂ 给 dynamic 发送悄悄话 (438 bytes) () 05/18/2009 postreply 19:55:29

• hmm，这个有意思：） -戏雨飞鹰- ♀ 给 戏雨飞鹰 发送悄悄话 戏雨飞鹰 的博客首页 (0 bytes) () 05/18/2009 postreply 21:12:19

• 回复：it takes a bit more than that -utopian- ♂ 给 utopian 发送悄悄话 (51 bytes) () 05/20/2009 postreply 17:23:11

• hashing needs linear memory as well. we want constant memory her -dynamic- ♂ 给 dynamic 发送悄悄话 (0 bytes) () 05/20/2009 postreply 17:28:12

• Pay attention to some key numbers. -乱弹- ♂ 给 乱弹 发送悄悄话 乱弹 的博客首页 (0 bytes) () 05/20/2009 postreply 19:24:24

• 觉得在哪里见过这个题目 -haha2000- ♂ 给 haha2000 发送悄悄话 (19 bytes) () 05/21/2009 postreply 07:24:10

• I don't think so. -乱弹- ♂ 给 乱弹 发送悄悄话 乱弹 的博客首页 (0 bytes) () 05/21/2009 postreply 09:52:29

• 这题目是IMB ２００４ 一月的一个puzzle：） -戏雨飞鹰- ♀ 给 戏雨飞鹰 发送悄悄话 戏雨飞鹰 的博客首页 (79 bytes) () 05/21/2009 postreply 12:22:12

• Yes, right! thanks! -haha2000- ♂ 给 haha2000 发送悄悄话 (0 bytes) () 05/22/2009 postreply 11:05:23

• solution -dynamic- ♂ 给 dynamic 发送悄悄话 (572 bytes) () 05/20/2009 postreply 21:41:18

• hmmm，佩服. "形状像一个勺子", haha... -戏雨飞鹰- ♀ 给 戏雨飞鹰 发送悄悄话 戏雨飞鹰 的博客首页 (0 bytes) () 05/21/2009 postreply 12:25:03

• 这个题目曾是微软的面试题目。但是没有了数组'read only'的条件， -戏雨飞鹰- ♀ 给 戏雨飞鹰 发送悄悄话 戏雨飞鹰 的博客首页 (75 bytes) () 05/21/2009 postreply 13:12:13

请您先登陆，再发跟帖！