删除单链表中的指定节点-ag真人游戏

题目1：

编写在带头结点的单链表l中删除一个最小值结点的高效算法（假设最小值结点是唯一的）。时间复杂度为o(n)，空间复杂度为o(1)。

问题解答：

算法思想：用p从头至尾扫描单链表，pre指向*p结点的前驱，用minp保存值最小的结点指针（初值为p），minpre指向*minp结点的前驱（初值为pre）。一边扫描，一边比较，若p->dafa小于minp->dara，则将p、pre分别赋值给minp、minpre，如下图所示。当p扫描完毕，minp指向最小值结点，minpre指向最小值结点的前驱结点，再将minp所指结点删除即可。

linklist delete_min(linklist &l){
    //l是带头结点的单链表，本算法删除其最小值结点
    lnode *pre = l, *p=pre->next;  //p 为工作指针，pre 指向其前驱
    lnode *minpre=pre, *minp=p;  //保存最小值结点及其前驱
    while(p!=null){
        if(p->datadata){
            minp=p;  //找到比之前找到的最小值结点更小的结点
            minpre=pre;
        }
        pre=p;  //继续扫描下一个结点
        p=p->next;
    }
    minpre->next=minp->next;  //删除最小值结点
    free(minp);
    return l;
}

题目：

删除带头结点的单链表l中的结点p，p不是最后一个结点，要求时间复杂度为o(1)。

问题解答：

如果删除的结点p可能是最后一个结点，怎么办？
解题思路：此时只能保证删除结点的平均时间复杂度为o(1)，当p不是最后一个结点，
时间复杂度为o(1)，当p是最后一个结点时，时间复杂度为o(n)。

struct listnode
{
	int value;
	listnode *pnext;
	listnode(int x):value(x), pnext(nullptr) {}
};
 
//p不是最后一个结点
void deletenode(listnode * &p)
{
	if(p==nullptr || p->pnext==nullptr)
		return;		//p为空，或是单链表中最后一个节点，不符合题意。
	listnode *temp_next=p->pnext;
	p->value=temp_next->value;
	p->pnext=temp_next->pnext;
	delete(temp_next);	//删除节点temp_next
	temp_next=nullptr;	//将节点置为空，防止它成为野指针
}

题目2：

如果删除的结点p可能是最后一个结点，怎么办？ 

解题思路：

此时只能保证删除结点的平均时间复杂度为o(1)，当p不是最后一个结点，
时间复杂度为o(1)，当p是最后一个结点时，时间复杂度为o(n)。

struct listnode
{
	int value;
	listnode *pnext;
	listnode(int x):value(x), pnext(nullptr) {}
};
 
void deletenode(listnode * &p)
{
	if(p==nullptr || p->pnext==nullptr)
		return;		//p为空，或是单链表中最后一个节点，不符合题意。
	if(p->pnext != nullptr)		//如果p不是最后一个节点
	{
		listnode *temp_next=p->pnext;
		p->value=temp_next->value;
		p->pnext=temp_next->pnext;
		delete(temp_next);	//删除节点temp_next
		temp_next=nullptr;	//将节点置为空，防止它成为野指针
	}
	else						//如果p是最后一个节点
	{
		listnode *phead;	//单链表的头结点指针phead
		listnode *pre=phead;
		while(pre->pnext!=p)
			pre=pre->pnext;
		pre->pnext=p->pnext;
		delete(p);
		p=nullptr;
	}
}