题目:实现一种算法,删除单向链表中间的某个节点(即不是第一个或最后一个节点),假定你只能访问该节点。

示例:

graph LR
A[a]-->B[b]
B[b]-->C[c]
C[c]-->D[d]
D[d]-->E[e]
1
2
输入:节点c
结果:不返回任何数据,将节点c从原链表中删除。

思路:这题的思路有点意思。首先我们只能访问到节点c,按照常规思路,如果我们要删除节点c,就要将c的上一个节点b指向c的下一个节点d,但我们只能访问节点cd,由于单向链表的特性,节点b我们是无法访问的。那我们该如何“神不知鬼不觉”的删除节点c呢?

“偷天换日”:我们的目标是让b指向d,但我们无法直接操作b,而b又一直指向c,所以我们只需要把c替换为d,然后再把d删除即可。

删不掉我自己(c),我就变成你(d),再删掉你(d),就等于删掉我自己(c)。

Java语言实现如下:

单链表节点类定义可查看文章:数据结构之链表-基础知识

1
2
3
4
5
6
public void deleteNode(SinglyLinkedListNode node) {
SinglyLinkedListNode next = node.next;
node.val = next.val;
node.next = next.next;
next = null;
}