O（1）条件下实现删除链表某个元素

在链表中，我们一般删除一个元素的方法是遍历找到他，然后将其前面的next指向他下一位，然而有一种时间复杂度为O（1）的方法，下面我们分析一下，这个方法就是如果他后面有元素，那么可以直接将下一个节点的值赋给该节点，然后令该节点指向下下个节点，再删除下一个节点，时间复杂度为 O(1)。

if(head==null||tobeDelete==null)
            return null;
        if(tobeDelete.next!=null)//如果要删除的节点后面有节点，那么直接将下一个节点的值赋给该节点
        {
            Link next=tobeDelete.next;
            tobeDelete.val=next.val;
            tobeDelete.next=next.next;
        }
        else{

            if(head==tobeDelete)//如果只有一个节点
            {
              head=null;
            }
            else {//如果要删除的在最后
                Link cur = head;
                while (cur.next != tobeDelete)
                    cur = cur.next;
                cur.next = null;

            }

            }
        return head;

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