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

题目：

给定单向链表的头指针和一个节点指针，定义一个函数在 O(1) 时间内删除该节点。链表节点与函数的定义如下：

public class ListNode {
    int value;
    ListNode next;
    public ListNode(int value) {
        this.value = value;
    }
}

public void deleteNode(ListNode head, ListNode targetNode) {

}

分析：

​ 最常见的做法是从头节点开始遍历链表，然后找到目标节点，把目标节点的上一个节点的 next 指向目标节点的 下一个节点(next)，那目标节点就被删除了。但这种方法在本题中显然不行，因为这样操作的时间复杂度是 O(n)。

O(1) 解法：

​ 已知目标节点 t，可以获得目标下一个节点 nt，然后可以获得 nt下一个节点 ntt。如果把 nt 的值复制给 t，然后把 nt 删除，则相当于把 n 给删除了，因为 n 的值没有了，保存的是 nt 的值。

注意：

​ 如果链表只有一个节点，则只需要把头结点删除即可。如果要删除尾结点，尾结点没有下个节点，只能通过逐个遍历的方法删除。

代码：

public void deleteNode(ListNode head, ListNode targetNode) {

    if (null == head || null == targetNode) {
        return;
    }

    if (targetNode.next != null) {
        // 要删除的节点不是尾结点
        ListNode nextNode = targetNode.next;
        targetNode.value = nextNode.value;
        targetNode.next = nextNode.next;
    } else if (targetNode == head) {
        // 链表只有一个节点，删除头结点（也是尾结点）
        head = null;
        targetNode = null;
    } else {
        // 链表中有多个节点，删除尾结点
        ListNode pNode = head;
        while (pNode.next != targetNode) {
            pNode = pNode.next;
        }
        pNode.next = null;
        targetNode = null;
    }
}

​ 上述方案，对于 n-1 个非尾结点而言，可以在 O(1) 的时间复杂度内覆盖要删除的节点，并删除下一个节点；对于尾结点而言，由于仍需要顺序查找，时间复杂度是 O(n)，因此总的时间复杂度是 [O(1) x (n-1) + O(n)] / n，结果是O(1)。

​ 由于 O(1) 时间限制，该方案没有判断要删除的节点是否存在于链表中，如果要判断的话需要 O(n) 的时间复杂度。所以需要调用者判断节点是否存在。