题目描述
给定单向链表的头指针head和一个节点指针p，定义一个函数在O(1)时间删除该节点p。
分析
在单向链表中删除一个节点，最常规的是从链表的头结点开始遍历，找到需要删除的节点并删除，平均时间复杂度为O(n)。
推荐解法
根据需要删除的节点指针p，可以找到p的下一个节点q，将q的值赋值给p后再将p的指针指向q，即用q覆盖p，则达到删除的目的。
- 如果链表中只有一个节点，在删除该节点后需要把链表的头结点置为null。
- 如果需要删除的是尾节点，即p的下一个节点q为null，则还是需要顺序遍历链表，找到p的前序节点进行删除操作。对于n-1个非尾节点，O(1)时间内可以删除，如果是尾节点则为O(n)，平均时间复杂度为$\frac{O(1)∗(n−1)+O(n)∗1}n$，时间复杂度还是O(1)。符合要求。不过该方法并没有判断需要删除的节点是否在链表中，为达到时间复杂度为O(1)的要求，将判断节点是否存在的责任推给了该方法的调用者。
/**
* 平均时间复杂度为O(1)，删除链表节点
* @param head 头结点
* @param nodeToBeDeleted 待删除节点
*/
public void deleteNode(ListNode head, ListNode nodeToBeDeleted) {
// 1.如果链表为空，或者待删除节点为空，返回
if(head == null || nodeToBeDeleted == null)
return;
// 待删除节点不是尾节点 O(1)
if (nodeToBeDeleted.next != null) {
nodeToBeDeleted.val = nodeToBeDeleted.next.val;
nodeToBeDeleted.next = nodeToBeDeleted.next.next;
} else if(head == nodeToBeDeleted) { // 链表中只有待删除节点 O(1)
nodeToBeDeleted = null;
head = null;
} else {
ListNode tmp = head; // 待删除节点为尾节点，而且链表有多个节点 O(n)
while (tmp.next != nodeToBeDeleted) {
tmp = tmp.next;
}
tmp.next = null;
nodeToBeDeleted = null;
}
}