《剑指offer》面试题18：在O（1）时间内删除链表节点
题目：给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间内删除该节点。（待删除节点一定在链表中）
思路：待删除节点的位置可能有三种情况，不同情况下的删除方式不同。
第一种情况：待删除节点位于含多个节点的链表的中间位置（不是尾节点），此种情况可用O(1)时间删除该节点。
删除方式：将当前待删除节点的下一个节点的数据域中的数据复制到该节点，然后让当前待删除节点的指针域（指向下一个节点的指针）指向该节点的下一个节点的下一个节点。最后把待删除节点的下一个节点删除。这样就相当于把当前待删除的节点删除了。
第二种情况：待删除节点位于含多个节点的链表的尾部：是尾节点。此种情况需要从头节点开始遍历链表，得到待删除节点的前一个节点，然后再删除待删除节点。时间复杂度O(n)。
第三种情况：待删除节点位于只有一个节点的链表的尾部：该链表只有一个节点，该节点既是头节点也是尾节点。直接删除该节点。
总的平均时间复杂度：((n-1)*O(1) + O(n))/n，结果为O(1)。
代码如下：
// 节点类
public class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
// 删除节点的方法
public ListNode deleteNode(ListNode head,ListNode toBeDeleted) {
if (head == null || toBeDeleted == null) {
return null;
}
if (toBeDeleted.next != null) {
// 不是尾节点
toBeDeleted.val = toBeDeleted.next.val;
toBeDeleted.next = toBeDeleted.next.next;
} else if (toBeDeleted == head) {
// 是尾节点，且也是头节点
return null;
} else {
// 是尾节点
ListNode tempNode = head;
while (toBeDeleted != tempNode) {
tempNode = tempNode.next;
}
tempNode.next = null;
}
return head;
}
