一亩三分地论坛

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

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

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

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

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

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

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

2.2 Implement an algorithm to find the kth to last element of a singly linked list.

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


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

bitcpf 发表于 2014-6-25 00:22:59 | 显示全部楼层
【解题思路】2 pointers, the first one move k steps then move the pointers together till the the first one touch the end of the list
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】https://gist.github.com/bitcpf/b66f30e9790e08189bb7
回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

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

【解题思路】先traverse linkedlist,获得linkedlist的长度N,在从头开始寻找第N-k+1个元素
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/chouclee/03cf7577a2ec37c6b311
回复 支持 反对

使用道具 举报

bearkino 发表于 2014-6-23 15:13:08 | 显示全部楼层
本帖最后由 bearkino 于 2014-6-23 15:21 编辑

【解题思路】
首先p1先走k步,然后p1,p2同时走,当p2走到尾端的时候,p1刚好在kth这个位置,距离尾端是k
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/UncleGarden/ab5491edaa4c81b08b3d
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-23 16:41:39 | 显示全部楼层
【解题思路】
首先p1先走k步,然后p1,p2同时走,当p2走到尾端的时候,p1刚好在kth这个位置,距离尾端是k
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/gaoyike/9eef63abd6756e1f13f8
回复 支持 反对

使用道具 举报

fang_wu 发表于 2014-6-23 19:24:26 | 显示全部楼层
【解题思路】
两个指针
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/qiangusc/d83a59d1efe2c95bf424
回复 支持 反对

使用道具 举报

grassgigi 发表于 2014-6-24 09:03:02 | 显示全部楼层
【解题思路】
Runner tech

【时间复杂度】
O(n)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/chrislukkk/a8edbb93ccd07acbdf0b
回复 支持 反对

使用道具 举报

林微熙 发表于 2014-6-24 14:13:21 | 显示全部楼层
【解题思路】
recursive
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】https://gist.github.com/hilda8519/c3d7f3fe212b926024bf
回复 支持 反对

使用道具 举报

aloncgo 发表于 2014-6-24 22:44:50 | 显示全部楼层
本帖最后由 aloncgo 于 2014-6-24 22:46 编辑

【解题思路】先获取总长度,再get倒数第k个
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/weazord/e37a37e895e9e406eafe
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-6-24 23:17:15 | 显示全部楼层
【解题思路】
two pointers p1 and p2, move p2 for k steps first, then move them together until p1 reaches the end of the list, p2 is the answer
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/iwilbert/700a22f8aca7b52544f5
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
length of the list is smaller than k
回复 支持 反对

使用道具 举报

heycinderella 发表于 2014-6-25 04:45:27 | 显示全部楼层
【解题思路】Use the runner technique. Use two pointers, move the runner k steps ahead
         * of the current pointer (if the runner reaches null it means k is larger
         * than the length, return null), then move them together one step at a
         * time. When the runner reaches the end the current points to the len-k th
         * element.
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/XiaoxiaoLi/d9b916553652fbeb6ef3
回复 支持 反对

使用道具 举报

jason51122 发表于 2014-6-25 13:53:29 | 显示全部楼层
To Be Implemented
回复 支持 反对

使用道具 举报

habina 发表于 2014-6-26 07:08:31 | 显示全部楼层
【解题思路】
  Two pointer point to head, first pointer move forward k elements, then move both pointer together, until the first one reaches the end, return second pointer.
【时间复杂度】
  O(N)
【空间复杂度】
  O(1)
【gist link】
  https://gist.github.com/habina/f521508cef301ac0d18d
回复 支持 反对

使用道具 举报

Neal 发表于 2014-6-26 09:14:39 | 显示全部楼层
【解题思路】Calculate the length of the list first, then get the (len-k-1)th element
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/nealhu/ff6cd5a1e217d47be280
回复 支持 反对

使用道具 举报

jason51122 发表于 2014-6-26 13:04:56 | 显示全部楼层

【解题思路】Use 2 pointers. Keep the distance between slow and fast pointer to k. Move the windows to the end.
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/jason51122/2873201611ad2675b5a3
回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-6-26 14:33:08 | 显示全部楼层
【解题思路】
2 pointers, the first one move k steps then move the pointers together till the the first one touch the end of the list
和 leetcode 上 Remove Nth Node From End of List 类似
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/JoyceeLee/2fa8f900432f8759c79f
回复 支持 反对

使用道具 举报

pud 发表于 2014-6-27 09:46:44 | 显示全部楼层
【解题思路】
  p1= head, p2指向第k个node。 一起遍历链表
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】https://gist.github.com/yokiy/7da78a4396e307ced78d
回复 支持 反对

使用道具 举报

RealityPC 发表于 2014-6-27 09:53:57 | 显示全部楼层
【解题思路】2 pointers
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/pchong90/1f91c296ccfb81a8b639
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-6-28 02:45:23 | 显示全部楼层
【解题思路】 use two pointers p1 and p2, which are k nodes apart. Iterate the list and stop when p2 hits the end.  
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/jyhjuzi/1c751226bdbb31ea3e78
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 20:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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