【第四轮】4.6 - 4.12 Career Cup 2.3

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

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. 
   
5. public static void bar() {
   
6.     ListNode node = new ListNode(1);
   
7.     foo(node);
   
8.     // right now, node.val == 10
   
9. }

复制代码

上面的例子中，foo函数成功的修改了输入参数的值

例子2-无法修改reference

1. public static void foo(ListNode node) {
   
2.     node = null;
   
3. }
   
4. 
   
5. public static void bar() {
   
6.     node = new ListNode(1);
   
7.     foo(node);
   
8.    // node is still pointing to 1, not null
   
9. }

复制代码

上面这个例子中，foo函数试图修改入参的reference，但是这个在 Java 中是不允许的。

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

【解题思路】 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

思路：关键是要找到待删除节点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)了。。

【解题思路】
因为题中说只给了middle的access，所以说只需要新建一个n.next点然后对data和指针进行操作就行了
【时间复杂度】
O（1）
【空间复杂度】
O（1）
【gist link]
https://github.com/JamesJi9277/C ... inkedLists/2.3.java
【test case】

【解题思路】
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)

【解题思路】
把中间点下一点的值赋给中间点，然后删除中间点的下一点
【时间复杂度】
O(1)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/alikewmk ... -2-3-delmiddle-java

【解题思路】
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

[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

【解题思路】
将 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