一亩三分地论坛

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

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

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

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

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

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

x
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 is returned, but the new linked list looks like a- >b- >d->e

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

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

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

JamesJi 发表于 2015-4-7 21:28:40 | 显示全部楼层
【解题思路】
因为题中说只给了middle的access,所以说只需要新建一个n.next点然后对data和指针进行操作就行了
【时间复杂度】
O(1)
【空间复杂度】
O(1)
【gist link]
https://github.com/JamesJi9277/C ... inkedLists/2.3.java
【test case】
回复 支持 反对

使用道具 举报

laonong15 发表于 2015-4-7 23:09:27 | 显示全部楼层
【解题思路】
set c.data = c.next.data   and  c.next= c.next .next
【时间复杂度】
O(1)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/michaelniu/dfd225dbbe0c11de83cb
【test case】
https://gist.github.com/michaelniu/dfd225dbbe0c11de83cb(main)
回复 支持 反对

使用道具 举报

slaink 发表于 2015-4-9 07:12:46 | 显示全部楼层
【解题思路】 Change the value of middle element, and delete next element
【时间复杂度】O(1)
【空间复杂度】O(1)

If given the head of the singly linked list, then we need to use two pointers to solve this, the time complexity is O(n)

【gist link] https://github.com/bxshi/intervi ... ete_middle_node.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)https://github.com/bxshi/intervi ... c/test/2_3_test.cpp
回复 支持 反对

使用道具 举报

coperdli 发表于 2015-4-10 15:57:09 | 显示全部楼层
思路:关键是要找到待删除节点p的前置节点prev, 然后将prev的next指向p->next,释放p指向的空间即可。
时间复杂度:平均需要遍历一半链表来发现p的前置节点,故而时间复杂度是O(n)
空间复杂度:O(1)
code snippet & test case: https://gist.github.com/coperd/8d4de6ec5f7b45b5e4a8

PS: @楼上给位怎么做到时间复杂度是O(1)的?????

补充内容 (2015-4-11 13:26):
晓得了O(1)了。。
回复 支持 反对

使用道具 举报

alikewmk 发表于 2015-4-10 16:14:42 | 显示全部楼层
【解题思路】
把中间点下一点的值赋给中间点,然后删除中间点的下一点
【时间复杂度】
O(1)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/alikewmk ... -2-3-delmiddle-java
回复 支持 反对

使用道具 举报

daphne_ying 发表于 2015-4-13 13:49:43 | 显示全部楼层
【解题思路】
if the node to be deleted is the last node of the linked list, return false, otherwise, copy the elem of the next node to the current node and delete the next node
【时间复杂度】
O(1)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/kelly-us/b87901c42b63eb44b93b
回复 支持 反对

使用道具 举报

A30041839 发表于 2015-4-13 21:49:10 | 显示全部楼层
[solution]
if the middle element is the last element(in this case, the linked list only has one element), then delete this node and return a null linkedlist; otherwise, copy the next element's value to the middle node, and delete the next element.
[time]
O(1)
[space]
O(1)
[gist]
https://gist.github.com/A30041839/8d781581af6a4027323c
回复 支持 反对

使用道具 举报

干.什么 发表于 2015-4-14 06:14:46 | 显示全部楼层
本帖最后由 干.什么 于 2015-4-14 06:21 编辑
laonong15 发表于 2015-4-7 23:09
【解题思路】
set c.data = c.next.data   and  c.next= c.next .next
【时间复杂度】

对不起我不会贴链接

在 Java 中输入的参数遵循 pass-by-value, 简单说就是你可以修改入参的值,但不能修改入参所对应的 reference。
例子1-可以修改入参的值
  1. public static void foo(ListNode node) {
  2.     node.val = 10;
  3. }

  4. public static void bar() {
  5.     ListNode node = new ListNode(1);
  6.     foo(node);
  7.     // right now, node.val == 10
  8. }
复制代码
上面的例子中,foo函数成功的修改了输入参数的值

例子2-无法修改reference
  1. public static void foo(ListNode node) {
  2.     node = null;
  3. }

  4. public static void bar() {
  5.     node = new ListNode(1);
  6.     foo(node);
  7.    // node is still pointing to 1, not null
  8. }
复制代码
上面这个例子中,foo函数试图修改入参的reference,但是这个在 Java 中是不允许的。

在你的代码里面,midNode = null; 这一行是不会生效的。其实这题不用想太多,这个方法很巧妙,仅此而已。你的实现已经很棒了,判断非法直接返回就好。

回复 支持 反对

使用道具 举报

干.什么 发表于 2015-4-14 06:19:45 | 显示全部楼层
【解题思路】
将 node.next 的值(如果存在)复制到node上面,然后将 node.next 删除

【时间复杂度】
O(1)
【空间复杂度】
O(1)
【gist link]
https://github.com/noisedispatch ... leteMiddleNode.java
【test case】(optional,如果觉得比较好,欢迎贴出来分享)
https://github.com/noisedispatch ... leteMiddleNode.java
回复 支持 反对

使用道具 举报

iker01 发表于 2015-4-14 09:41:26 | 显示全部楼层
【解题思路】
# set the next value to the current middle node
# set the next next node to middle node's next
# if the final node, set to None
【时间复杂度】
O(1)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/zhangjiang2013/29876ad7c028aaf72800
回复 支持 反对

使用道具 举报

sevenwonder 发表于 2015-4-19 11:56:43 | 显示全部楼层
【解题思路】
set c.data=d.data, then delete d.考虑好 c的各种情况比如在头 尾, 或者为空。
  
【时间复杂度】
O(1)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/songpu2015617/30a68118bc70eccd5944
回复 支持 反对

使用道具 举报

Godbless 发表于 2015-5-27 10:37:58 | 显示全部楼层
【解题思路】Simply copy the next node to the middle node and then delete the next node
【时间复杂度】O(1)
【空间复杂度】O(1)
【gist link] https://github.com/StephenWeiXu/ ... aster/Chap2/2_3.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)
回复 支持 反对

使用道具 举报

hli42 发表于 2015-5-28 10:40:38 | 显示全部楼层
【解题思路】Make the current node's value equal to its next and delete the next node.
【时间复杂度】O(1)
【空间复杂度】O(1)
【gist link]https://gist.github.com/hli42/bf0168666f8f66196aaf
【test case】
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 03:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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