Cracking Coding Interview - 2.3 Delete Middle Node

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;
}

版权

评论