一亩三分地论坛

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

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

[CareerCup] 【第四轮】4.6 - 4.12 Career Cup 2.6

[复制链接] |试试Instant~ |关注本帖
pure0909 发表于 2015-4-7 01:48:14 | 显示全部楼层 |阅读模式

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

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

x
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 [the same C as earlier]
Output: C

请参加活动的童鞋跟帖回复自己的解法,回复请参考以下格式:

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link]
【test case】(optional,如果觉得比较好,欢迎贴出来分享)

Notice:
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子,除了贴解法,欢迎探讨各种follow up questions,集思广益
4、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改


JamesJi 发表于 2015-4-9 23:32:18 | 显示全部楼层
【解题思路】
用快慢指针,快的一次走两步,慢的一次一步,找到他们相遇点然后快慢指针同时一次走一步,下一次相遇点就是loop开始的地方
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/JamesJi9277/52356b141d58557635bd
【test case】
回复 支持 反对

使用道具 举报

laonong15 发表于 2015-4-10 02:22:40 | 显示全部楼层
【解题思路】
I hate the solution from  book :(   here is  mine :

Assume the   node  data is unique for the simplify,  we also can add  a "key" as the unique flag
1. user fast and  slow pointer find  a  the   circle and get  the collide spot ,
2. use hashtable  to  store all the  nodes of circle
3. traverse the list from the head,  get the first one that exist in hashtable.
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link]
https://gist.github.com/michaelniu/04bd0de9b9f1edded0b5
【test case】
https://gist.github.com/michaelniu/04bd0de9b9f1edded0b5(main)
回复 支持 反对

使用道具 举报

slaink 发表于 2015-4-13 05:58:53 | 显示全部楼层
【解题思路】
/**
* Find the starting point of a loop in a singly linked list.
*
* First use two pointers, one moves 1 step every time and the other
* one moves 2 steps per time. Then when the slow pointer reaches
* the starting point of the loop, the fast pointer is at k%m position in
* the loop (where k is the distance between the start of the list and the start
* of the loop, and m is the length of the loop). When slow and fast pointers meet,
* it is at m - k%m position. Then we need move the slow pointer back to the
* head, and when these two pointers meet again, it is the starting point
* of that loop.
*
* Time complexity: O(n)
* Space complexity: O(1)
*
*/
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link] https://github.com/bxshi/intervi ... /2_6_find_cycle.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)https://github.com/bxshi/intervi ... c/test/2_6_test.cpp
回复 支持 反对

使用道具 举报

daphne_ying 发表于 2015-4-13 13:59:57 | 显示全部楼层

【solution】
a tricky solution from the book: use two pointers, slow runner moves 1 step every time and  fast runner moves 2 step. When the slow runner catches up with the fast runner, the hit point are k steps from the beginning of the loop, where k is the steps between the head node and the beginning of the loop.
【time】
O(n)
【space】
O(1)
【gist link]
https://gist.github.com/kelly-us/583a0b4394c6b7eedd31
回复 支持 反对

使用道具 举报

alikewmk 发表于 2015-4-14 01:44:03 | 显示全部楼层
【解题思路】
快慢指针
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/alikewmk ... -6-checkcircle-java
回复 支持 反对

使用道具 举报

iker01 发表于 2015-4-14 09:06:51 | 显示全部楼层
【解题思路】
# Use fast and slow pointers to find the collision node
# Set fast pointer to head and traverse again which moves one step each time
# Move slow pointer at the same time
# find the collision node
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/zhangjiang2013/592c00a7b3178807e644
回复 支持 反对

使用道具 举报

coperdli 发表于 2015-4-14 15:11:42 | 显示全部楼层
本帖最后由 coperdli 于 2015-4-14 15:12 编辑

思路:自己没想出来,后来google发现这其实是个cycle detection的经典问题,著名的Floyd's cycle-finding algorithm就是龟兔赛跑式:(1). 第一程,兔的速度是龟的两倍,跑呀跑知道两者相遇。因为有loop,所有两者必然在loop中的某处相遇 (2). 把龟放回起点,🐰位置不变,两者同时以同速接着跑,这次他们相遇的点就是loop的起点。 一个比较通俗易懂的数学解释(证明)见http://stackoverflow.com/questio ... e-linked-list-work#那个100+ vote的回答

时间复杂度:取决于他们第一次相遇在loop里转了多少圈,就是第一次相遇龟跑的距离
空间复杂度:O(1)
code snippet & test case: https://gist.github.com/coperd/3ae90a32432dd4229ee0
回复 支持 反对

使用道具 举报

sevenwonder 发表于 2015-4-22 12:12:53 | 显示全部楼层
【解题思路】
1.快慢指针。 2.hashtable
【时间复杂度】
1 O(n), 2. O(n)
【空间复杂度】
1. O(1) 2. O(n)
【gist link】
https://gist.github.com/songpu2015617/eea86116db12bddcba70
回复 支持 反对

使用道具 举报

Godbless 发表于 2015-5-31 11:27:08 | 显示全部楼层
【解题思路】Use two pointers: slow pointer and fast pointer. Move fast pointer 2 spaces each time and
        move slow pointer 1 space each time. The two pointers will meet in the loop. Then move slow pointer
        to the head, and increase both slow pointer and fast pointer with 1 space each time. They will meet
        in the start node of the loop.
【时间复杂度】 O(n)
【空间复杂度】O(1)
【gist link] https://github.com/StephenWeiXu/ ... aster/Chap2/2_6.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 09:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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