【36】在O(1)的时间删除链表结点

题目：给定一个单向链表（只有指向下一个结点的指针）的头结点和某一个结点的指针，求怎样在O(1)的时间删除这个给定结点。

分析：

1.  最朴素的算法是从头结点开始搜索到给定结点前一个结点，然后把结点删除。这种方法的时间复杂度为0(n)，所以不能在O(1)的时间内删除该结点

2. 要求在O(1)的时间内删除某个结点，肯定是利用单向链表的性质。给定单向链表只有指向下一个结点的指针，我们无法得到前面一个结点的指针。所以我们可以考虑换个思路。

    （1）假设要删除的链表如下

    （2）因为给定结点2的指针，那么通过下一个结点指针可以得到结点3的指针。所以实际上删除结点2等价于把结点3复制一份到结点2中，然后删除结点3，如下图

   （3）所以实际上，就是把给定结点的下一个结点复制给当前结点然后删除下一个结点。这样就可以在O(1)的时间内删除某一个结点

注意：

1. 由于涉及到下一个结点，所以要考虑多种情况

  （1）删除结点是头结点

  （2）删除结点在中间，既不是头结点也不是尾结点

  （3）删除结点是尾结点

2. 对于这些情况要分类讨论 

   总的分成两类，删除结点的下一个结点是否为空和不空

   （1）如果删除结点的下一个结点为空，说明删除结点是尾结点。则这个时候要采用从头遍历，因为没有办法把空结点复制给当前结点，这个是必须O(n)枚举。注意链表有且仅有一个结点并删除尾结点情况

   （2）如果删除结点的下一个结点不为空，则直接把下一个结点复制给当前结点，然后删除下一个结点即可

代码：

//链表结点
struct ListNode{
    int value;
	ListNode *nextNode;	   
};

//删除一个结点，涉及到修改指针传递指针的指针 
void DeleteNode(ListNode **headNode, ListNode **deleteNode){
    //不合法数据
	if((*headNode) == NULL || (*deleteNode) == NULL){
	    return;
    } 
    //删除结点
	ListNode *deleteNodeNextNode = (*deleteNode)->nextNode;
	//如果下一个结点是为空，直接删除该点 
	if(deleteNodeNextNode == NULL){
        //遍历删除
		ListNode *tmpNode = (*headNode);
		while((tmpNode != NULL) && (tmpNode->nextNode != (*deleteNode))){
		      tmpNode = tmpNode->nextNode;
	    } 
	    //如果当前链表有且只有一个点则tmpNode变成NULL 
	    if(tmpNode != NULL){
		    tmpNode->nextNode = NULL;
		}
		delete (*deleteNode);
		(*deleteNode) = NULL; 
    } 
    else{
        //把下一个结点值复制给当前结点 
		(*deleteNode)->value = deleteNodeNextNode->value;
        (*deleteNode)->nextNode = deleteNodeNextNode->nextNode;
         //删除下一个结点 
		 delete deleteNodeNextNode;
		 deleteNodeNextNode = NULL;
    }
}