一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1601|回复: 28
收起左侧

[CareerCup] 【第三轮】6.23-6.29 CareerCup 2.6

[复制链接] |试试Instant~ |关注本帖
wrj5518 发表于 2014-6-23 00:00:09 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 wrj5518 于 2014-6-23 09:33 编辑

2.6
Given a circular linked list, implement an algorithm which returns the node at the beginning of the loop.
DEFINITION
Circular linked list: A (corrupt) linked list in which a node's next pointer points to an earlier node, so as to make a loop in the linked list.
EXAMPLE
Input:A ->B->C->D->E-> C[thesameCasearlier]
Output:C

回复解法可以按照以下格式来
【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------optional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】


Notice:
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子,除了贴解法,欢迎讨论,集思广益
4、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改。
grassgigi 发表于 2014-6-26 09:58:55 | 显示全部楼层
本帖最后由 grassgigi 于 2014-6-26 10:01 编辑

【解题思路】
龟兔赛跑
Proof:
K -- number of nodes before cycle start point in list
C -- number of nodes of cycle
Let the faster nodes forward 2 steps each turn, slow nodes forward 1 step each turn.
S -- how many steps slow node passed when two nodes meet.
X -- the node distance between the meet point and cycle start point

When two meet each other, lets say first nodes go through whole cycle M times, second nodes go through whole cycle N times, we have:

equation 1 => S = K + M *C + X
eq 2 => 2S = K + N * C + X

eq 2 - eq 1 => S  = (N - M) * C
Replace S in eq 1 => X = (N - M)C - K - M = (N - 2M)C - K

So at their meeting point, after K more steps the slower node will arrive the cycle start.
Inorder to do that we just need to put the fast node back to head and go one step forward each time, as well as slow node, until they meet each other again in the cycle start point

【时间复杂度】
O(N)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/chrislukkk/f452d108f42cc6a52110

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

头像被屏蔽
serolins 发表于 2014-6-29 00:42:38 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 1 反对 0

使用道具 举报

readman 发表于 2014-6-23 11:14:40 | 显示全部楼层
【解题思路】
我还真不知道除了书上的技术, 还有什么好办法..计数法好像也可以..不过要先扫一下有多少个不同的元素.
【时间复杂度】
n, if there is a loop
【空间复杂度】
1
【gist link】
https://gist.github.com/gaoyike/f319f54ad7e9b9c4adea
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
回复 支持 反对

使用道具 举报

chouclee 发表于 2014-6-23 12:49:11 | 显示全部楼层
本帖最后由 chouclee 于 2014-6-23 14:53 编辑

【解题思路】Java利用object的hashcode(),用HashSet<Integer>存储每个object的hashcode(),遇到hashcode()一致的,则认为遇到了之前的object (参考了hawstein大神的算法)
C++可以对object的首地址进行hash
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/chouclee/02602d805ed9640ab10d
回复 支持 反对

使用道具 举报

bearkino 发表于 2014-6-25 02:03:44 | 显示全部楼层
【解题思路】
书上很经典的解法,一般list中取一个点,普遍会想到采用快慢指针的概念。
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/UncleGarden/7542e36e48a297042df9
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-6-25 06:16:26 | 显示全部楼层
【解题思路】
using fast (2x) and slow (1x) pointers, when they meet, assign fast pointer to the beginning of the list, and the next time they meet is the beginning of the loop.
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/iwilbert/0c73b9dadb9cac4a0fa0
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
no loop should return null
回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-6-27 08:18:10 | 显示全部楼层
【解题思路】
the same as Linked List Cycle II in leetcode. set a fast point and a slow point.
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/JoyceeLee/8358b4b671949731cc42
回复 支持 反对

使用道具 举报

林微熙 发表于 2014-6-27 12:54:13 | 显示全部楼层
【解题思路】
using fast (2x) and slow (1x) pointers, when they meet, assign fast pointer to the beginning of the list, and the next time they meet is the beginning of the loop. I used the method in the book
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】https://gist.github.com/hilda8519/2a4317a8d9fa1a9b8056
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-6-28 08:56:30 | 显示全部楼层
【解题思路】  faster and slower runner
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】  https://gist.github.com/jyhjuzi/d1238d32b9453e37167e
回复 支持 反对

使用道具 举报

kimi81017 发表于 2014-6-28 12:49:11 | 显示全部楼层
【解题思路】  
快慢指针
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/WOLOHAHA/aff331d845cc880ccab3
回复 支持 反对

使用道具 举报

habina 发表于 2014-6-28 17:12:44 | 显示全部楼层
"""
============================================================================
Solution        : Faster pointer moves two steps at a time,
                    slower pointer moves onw step at a time,
                    after their first time meet,
                    reset fater pointer back to head
                    return slower when they meet again
Time Complexity : O(n)
Space Complexity: O(1)
Gist Link       : https://gist.github.com/habina/d8bbd5fbe1567502c676
============================================================================
"""
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-6-29 05:09:24 | 显示全部楼层

【解题思路】  No idea till read the book... faster pointer and slower pointer, slower pointer move 1 step each time, faster pointer move 2 steps each time. When they meet, assign one of them as the header of the linked list, when they meet again, output the node
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】 https://gist.github.com/bitcpf/7790d1e5f963ae582fe2
回复 支持 反对

使用道具 举报

pud 发表于 2014-6-29 08:02:08 | 显示全部楼层
【解题思路】 看书上的解法,用快慢指针
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】 https://gist.github.com/yokiy/da71157d9de7dc6491ba
回复 支持 反对

使用道具 举报

heycinderella 发表于 2014-6-29 09:51:47 | 显示全部楼层

【解题思路】 用HashSet存每个node,遇到一样的就返回。再就是书上space O(1)的解法了
【时间复杂度】
O(N)
【空间复杂度】
O(n)
【gist link】 https://gist.github.com/XiaoxiaoLi/2dcd9f629fef8469a1f7
回复 支持 反对

使用道具 举报

jing0328 发表于 2014-6-29 17:06:35 | 显示全部楼层
【解题思路】assume one loop in the list, use a hashset to store node, traverse the list and see if a node has already been in the set
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/startupjing/33c7e74aca2ab63441ae
回复 支持 反对

使用道具 举报

Neal 发表于 2014-6-30 11:08:23 | 显示全部楼层
【解题思路】Use fast and slow runner. If fast and slow runner meet, there is a loop.
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/nealhu/e333fc1162464261f663
回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-6-30 11:57:43 | 显示全部楼层
本帖最后由 ivycheung1208 于 2014-6-29 23:00 编辑

【解题思路】
1. Floyd's algorithm
2. Brent's algorithm
C.f. wiki page: cycle detection
【时间复杂度】
O(λ + μ)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/04fef6f51373925ab3a6
【test case】
null list
no loop
common case
回复 支持 反对

使用道具 举报

aloncgo 发表于 2014-7-1 10:50:44 | 显示全部楼层
【解题思路】Fast/Slow 指针
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/weazord/8ddffcbd65ed86fb00aa
回复 支持 反对

使用道具 举报

jason51122 发表于 2014-7-2 14:00:05 | 显示全部楼层
【解题思路】Use slow and fast pointers. When they meet, move slow pointer to head. Then move two pointers with the same pace until they meet.
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/jason51122/cafb1093ab8fb82ee0b0
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 18:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表