[第二轮] 2/25-3/3 CareerCup 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

发帖规范:
http://www.1point3acres.com/bbs/thread-48094-1-1.html
http://www.1point3acres.com/bbs/thread-32423-1-1.html

Some comment in the solution:

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

two pointer, one slow and another one one node fast.

Just assign both value and pointer of  node.next.next to current node
need check the null
https://gist.github.com/mazl123321/5024452

题目看错了，以下是将链表头作为输入的。。。

使用两个“指针”（借用C/C++里的说法），第一个遍历链表，第二个初始设置为空，当第一个指针移动至第三个节点时激活第二个指针（指向head)， 从此以后第一个指针每移动两次，第二个指针移动一次。当第一个指针移至末尾时，第二个指针会指向中间节点的前一个，然后你懂的。
链表为空或是长度小于3另行处理。
run time complexity O(N), storage complexity O(1)

https://gist.github.com/Zuohr/5027743

mazl123321 发表于 2013-2-25 00:35
Just assign both value and pointer of  node.next.next to current node
need check the null
https:// ...

你可能误解题目意思了，你的函数只能处理长度为5的链表。题目的意思应该是输入任何长度的链表都能做出正确的处理。

zuohr 发表于 2013-2-25 12:36
你可能误解题目意思了，你的函数只能处理长度为5的链表。题目的意思应该是输入任何长度的链表都能做出正确 ...

不好意思我自己看错了。。。

https://gist.github.com/mettaworld/5029511
java language

zuohr 发表于 2013-2-25 12:30
题目看错了，以下是将链表头作为输入的。。。

使用两个“指针”（借用C/C++里的说法），第一个遍历链表， ...

I think  you method seems a little too complicated. My algorithm is something similar to mazl123321. I think we should not be fooled by the word "delete". I know, your algorithm is trying to find the previous node of the given node so that we can correctly delete. But to achieve the same side effect causing by this deletion, we can simply change the value of the current node to the value of the next one. In this way, we can have the resulted list that looks like we have deleted the given node. And this algorithm only requires to iterate one time, also, it is very easy to implemented.

ryancooper 发表于 2013-2-26 09:32
I think  you method seems a little too complicated. My algorithm is something similar to mazl12332 ...

对的，我的解法是看错了题目的，以为输入是链表的头。。。

* Method: Copy the next node to the deleting node, then delete the next node.
* Bug: Cannot delete the last node, don't know what's wrong.
C language:https://gist.github.com/hukun01/5037016

Could anyone help?

不大清楚什么是given only access to that node，that node是指head还是要删的node。。。还有怎么处理链表长度为偶数的情况，比如a->b是不改还是得到b；a->b->c->d是得到a->c->d还是a->b->d还是不改。。。