📣 VIP通行证夏日特惠 限时立减$68
查看: 2751| 回复: 13
跳转到指定楼层
上一主题 下一主题
收起左侧

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

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改


上一篇:【第四轮】4.6 - 4.12 Career Cup 2.2
下一篇:【第四轮】4.6 - 4.12 Career Cup 2.4
推荐
干.什么 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; 这一行是不会生效的。其实这题不用想太多,这个方法很巧妙,仅此而已。你的实现已经很棒了,判断非法直接返回就好。

回复

使用道具 举报

推荐
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)了。。
回复

使用道具 举报

🔗
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)
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-MIEFA  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: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
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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