对于一个单项链接的链表，给定其中某个任意节点，要求在O(1)的时间复杂度内删除该节点。表面上看起来，似乎不可能做到，因为如果要求时间复杂度是O(1)的话，那意味着，算法实现中，不得包含有任何循环或是对链表的整体遍历。
但问题在于，要删除某个指定节点，我们需要通过遍历，找到该节点的前节点，然后修改前节点的next指针，这样才能正常的删除当前节点。
但如果给定的节点不是链表的末尾节点的话，那么要做到这一点就不难，只需要一点小技巧就可以实现，于是，问题转换如下：
假设节点v是单项链接链表中的某个节点，并且确保v不是链表的尾节点，要求在O(1)的时间复杂度内删除该节点.
例如给定链表如下：
给定的节点v就是值为3的节点，要求在O(1)的时间内删除该节点，并且不能使用多余内存。
一般做法是找到节点3的前节点，也就是节点2，然后把节点2的next指针指向节点4，但由于我们不能从头遍历，所以我们无法找到节点2.
但是我们可以使用个小技巧，把节点4的值拷贝到节点3，然后把节点3的next指针指向节点5，那就可以了：
具体代码实现如下：
public class NodeDelete {
public void deleteNode(Node node) {
if (node.next == null) {
return ;
}
node.val = node.next.val;
node.next = node.next.next;
}
}主入口处的代码如下：
public class LinkList {
public static void main(String[] args) {
ListUtility util = new ListUtility();
Node head = util.createList(10);
System.out.println("Link list before node deletion:");
util.printList(head);
Node n = util.getNodeByIdx(head, 3);
NodeDelete nd = new NodeDelete();
nd.deleteNode(n);
System.out.println("Link list after node deletion: ");
util.printList(head);
}
}首先构建一个含有5个节点的单向链表，然后获得值为3的节点，先把节点删除前的链表打印出来，然后调用算法实现删除指定节点，最后再把删除后的链表打印出来，运行后结果如下：
Link list before node deletion:
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
Link list after node deletion:
0 -> 1 -> 2 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
由此可见，我们的算法实现是正确的，同时在算法实现中，我们并没有使用循环去遍历队列，只是对节点的next指针做一些操作，因此算法的时间复杂度确实是O(1).
问题的解法看起来相当简单，但问题在于，在面试中，你处于一种紧张的压力状态之下，同时思考时间有限，有了想法后，还得把代码写出来，并且保证代码不出错，因此，看似简单的题目，在有限的时间约束和一定的心理压力之下，想顺利的解决，也不是一件容易的事情。
更多技术信息，包括操作系统，编译器，面试算法，机器学习，人工智能，请关照我的公众号：
