一亩三分地论坛

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

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

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

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

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

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

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

2.3
Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node.
EXAMPLE
Input: the node c from the linked list a->b->c->d->e
Result: nothing isreturned, but the new linked list looks like a- >b- >d->e

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


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

readman 发表于 2014-6-23 01:12:34 | 显示全部楼层
【解题思路】
runner tech
【时间复杂度】
n
【空间复杂度】
1
【gist link】
https://gist.github.com/gaoyike/9088a0cc8d2d6af7694f
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

qianhuang 发表于 2014-6-23 10:21:14 | 显示全部楼层
【解题思路】
assign the value of its next to the node p, then delete the its next. consider following case:
   1. p is the middle node
   2. p is the last node (need to get more information from interviewer)
   3. p is the head
【时间复杂度】
O(1)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/qianhuang/4621219abc5b2e3153fb

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

chouclee 发表于 2014-6-23 11:26:26 | 显示全部楼层
【解题思路】将后一个node的所有信息复制给当前node,再删除后一个node。这么做的问题在于,实际当前node并没有被删除,如果还想要删除后一个node,程序会出错
【时间复杂度】O(1)
【空间复杂度】O(1)
【gist link】https://gist.github.com/chouclee/9b6beccbba1579ac0247

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

fang_wu 发表于 2014-6-23 19:27:29 | 显示全部楼层
【解题思路】将当前node的信息全都给后一个,同时删除前一个,但是如果是最后一个就不好考虑,那么可以设置为最小值,不打印出来
【时间复杂度】O(1)
【空间复杂度】O(1)
【gist link】https://gist.github.com/qiangusc/57bd879cda8daf6f0b2b

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

bearkino 发表于 2014-6-23 22:56:16 | 显示全部楼层
【解题思路】
如果只是传入node,对node进行操作,那么就是copy当前需要删除的node的下一个结点的数据到当前结点,然后当前结点连接下一个结点的next,跳过下一个结点,即删除了当前结点。

如果需要输出整个list,传入当前list, 和k值,for loop不添加需要删除的结点即可
【时间复杂度】
O(1)/ O(n)
【空间复杂度】
O(1)/ O(n)
【gist link】
https://gist.github.com/UncleGarden/f19d7c4a4a7666ef5144

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

grassgigi 发表于 2014-6-24 09:31:01 | 显示全部楼层
【解题思路】
Copy data of next node to the current node and delete next node.
For the last node, we should consider it specially. since Java always pass value to function(even for reference), so there is no way to set the last node to null. (now I miss my C# and ref..)

【时间复杂度】
O(1)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/chrislukkk/37c7a2b140795abff900

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

林微熙 发表于 2014-6-24 15:24:15 | 显示全部楼层
【解题思路】
把下一个复制到这个,删下一个
【时间复杂度】
1
【空间复杂度】
1
【gist link】https://gist.github.com/hilda8519/00ffa4ba7b468b6f6e85

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

wilbert 发表于 2014-6-25 03:25:43 | 显示全部楼层
【解题思路】
copy the value of next node to the node given (to be deleted), and delete the next node. The following conditions are NOT considered.
(1) given node at the beginning
(2) given node at the end
【时间复杂度】
O(1)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/iwilbert/e32064c46369092cba64

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

aloncgo 发表于 2014-6-25 23:04:31 | 显示全部楼层
【解题思路】空node/最后一个node不可能删除,返回;  
该node复制下一个node的全部信息,这样实际上是删除下一个node,但用下一个node的值替换了想要删除的node的值
【时间复杂度】O(1)
【空间复杂度】O(1)
【gist link】https://gist.github.com/weazord/054b3fd99671699db121

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-6-26 00:52:45 | 显示全部楼层
【解题思路】empty/last node could not be deleted. copy the data from the next node to current node, and link current node to next.next node
【时间复杂度】O(1)
【空间复杂度】O(1)
【gist link】https://gist.github.com/bitcpf/943a20fc760f8ca4f6d3

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

heycinderella 发表于 2014-6-26 02:45:11 | 显示全部楼层
本帖最后由 heycinderella 于 2014-6-26 02:55 编辑

【解题思路】
// Ask the interviewer if this means that the middlenode won't be the first or the last. If it is the first it doesn't matter. However if it is the last it can't be deleted. I assume the node that is to be deleted is not the last.

* Copy the value of each following node back one step, and put null after the 2nd to last node.
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/XiaoxiaoLi/f4ebb8143890558ac5ff

做完才发现书里答案那么简单,智商啊。。。其实就是把n下一个node的data copy过来,然后直接删掉n.next即可。。。那样时间空间都是O(1)了吧

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

头像被屏蔽
serolins 发表于 2014-6-26 04:01:28 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

habina 发表于 2014-6-26 07:33:52 | 显示全部楼层

【解题思路】
Copy the following pointer content, and relink the next to the next next pointer
【时间复杂度】
O(1)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/habina/1effe686ec65dbadf1ec

补充内容 (2014-6-28 10:18):
@ivycheung1208 嗯,是的,谢谢提醒,我准备用python重写

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-6-27 06:29:14 | 显示全部楼层
【解题思路】
只是传入node,那么copy当前需要删除的node的下一个结点的数据到当前结点,然后当前结点连接下一个结点的next
【时间复杂度】
O(1)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/JoyceeLee/16128f844bfb476eb21c

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Neal 发表于 2014-6-27 10:20:20 | 显示全部楼层

【解题思路】Move the value of the next node to current node, remove next node. It's impossible if current node is the last node in the list.
【时间复杂度】O(1)
【空间复杂度】O(1)
【gist link】https://gist.github.com/nealhu/f5dcf011d595afa43278

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

jason51122 发表于 2014-6-27 14:04:32 | 显示全部楼层
【解题思路】Update the current node's value to the next node's value. Skip the next node.
【时间复杂度】O(1)
【空间复杂度】O(1)
【gist link】https://gist.github.com/jason51122/94802d43cf85c27ccd29

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

pud 发表于 2014-6-28 01:42:00 | 显示全部楼层
【解题思路】
  把next node的data给当前的node,再删除next node
【时间复杂度】
   O(1)
【空间复杂度】
   O(1)
【gist link】https://gist.github.com/yokiy/b5bbba6b2bdb36327a29

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-6-28 02:59:24 | 显示全部楼层
【解题思路】 copy  the data from the next node over to the current node, remove the next node
【时间复杂度】O(1)
【空间复杂度】O(1)
【gist link】https://gist.github.com/jyhjuzi/3cf87cd4799352c6e4d9

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-6-28 09:55:24 | 显示全部楼层
【解题思路】
***from solution***
copy data from the next node over, then delete the next node
(assume data type is integer)
【时间复杂度】
O(1)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/637c9366423ebd2ad8f0
【test case】
n = 0, list = {1, 2, 3, 4} invalid index
n = 1, list = {1, 2, 3, 4} delete the first element
n = 4, list = {1, 2, 3, 4} cannot delete the last element
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 00:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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