在O(1)时间内删除链表节点

《剑指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;
}