问题一：在O(1)时间内删除链表节点

• 如果我们把下一个节点的内容复制到需要删除的节点上覆盖原有的内容，再把下一个节点删除
• 如果要删除的节点位于链表的尾部,仍然从链表的头节点开始，顺序遍历得到该节点的前序节点，并完成删除操作
• 如果链表只有一个节点，而我们又要删除链表的头节点（也是尾节点）,在删除节点之后，还需要把链表的头节点设置为null

public class E18DeleteOneListNode {

    private static class ListNode{
        //链表结构
        int value;
        ListNode nextNode;
    }

    //没有考虑到待删除节点不在链表中的情况
    public static void deleteOneListNode(ListNode head, ListNode nodeToBeDeleted){
        if (head == null || nodeToBeDeleted == null)
            return;
        //待删除节点不是尾节点
        if (nodeToBeDeleted.nextNode != null){
            ListNode node = nodeToBeDeleted.nextNode;
            nodeToBeDeleted.value = node.value;
            nodeToBeDeleted.nextNode = node.nextNode;
        }
        //又是尾节点又是头节点
        else if (head == nodeToBeDeleted){
            head = null;
        }
        //是尾节点但不是头节点
        else{
            ListNode node = head;
            while(node.nextNode != nodeToBeDeleted){
                node = node.nextNode;
            }
            node.nextNode = null;
        }
    }
}

对于n-1个非尾节点而言，我们可以在O(1)时间内把下一个节点的内存复制覆盖要删除的节点，并删除下一个节点；对于尾节点而言，由于仍然需要顺序查找，时间复杂度是O(n)。因此，总的平均复杂度是[(n-1)xO(1)+O(n)]/n，结果还是O(1)

因为它基于一个假设：要删除的节点的确在链表中。我们需要O(n)的时间才能判断链表中是否包含某一节点。受到O(1)时间的限制，我们不得不把确保点在链表中的责任推给了函数DeleteNode的调用者。

参考

删除链表的节点（Java实现）