Delete Middle Node: Implement an algorithm to delete a node in the middle (i.e., any node but the first and last node, not necessarily the exact middle) of a singly linked list, given only access to that node.
EXAMPLE
1
2
3
|
Input: the node c from the linked list a->b->c->d->e->f
Result: nothing is returned,
but the new linked list looks like a->b->d->e- >f
|
分析
这个问题是如果你能够访问到某个node,那么怎么删除掉这个node,而且你没有办法访问head node。
因为没有办法获得前驱指针,那有没有办法把后面的提到前面去?似乎可以通过copy data的方式看上去像把node提前了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
v
a -> b -> c -> d -> e ->f
把data复制过来:
v
a -> b -> d -> d -> e ->f
指向next.next
a -> b -> d d -> e ->f
\_______/
孤立next
a -> b -> d d e ->f
\_______/
|
代码:
1
2
3
4
5
6
7
8
|
public void deleteNode(Node node) {
if (node == null || node.next == null) {
return;
}
node.data = node.next.data;
node.next = node.next.next;
node.next.next = null;
}
|
评论