Question

已知一个带有表头结点的单链表，结点结构为（info,next),假设该链表只给出了指针head。

请设计一个尽可能高效的算法，在单链表中删除一个最小的节点。要求：
1，描述算法的基本设计思想和详细实现步骤；
2，根据设计思想和实现步骤，采用程序设计语言描述算法，关键之处请给出简要注释。

Answer 1

1.大概思想就是搜索这个链表的最小值，搜索的同时记录下最小值结点的前驱pre及结点本身minNode，搜索完毕后，直接将前驱pre连到minNode之后，即跳过了最小值的那个结点

[XXX] -> [minpre] ->[minNode] ->[XXX]

变成
[XXX] -> [minpre] ->[XXX]

代码如下：
//删除值最小结点
void RemoveminNode(Node *&head)
{
//找到节点最小节点
int min = head->info; //暂定最小值为head的，如果head为空值的话，此处可改为head->next->info

Node *curr = head->next; //记录当前搜索的结点
Node *pre = head; //记录当前搜索的前一个结点
Node *minpre = head;//记录最小结点
Node *minNode = head;//记录最小结点的前驱结点
while (curr != NULL ) // 开始搜索并记录
{
if (curr->info < min) //如果比当前还小
{
minpre = pre;
minNode = curr;
}
else
{
pre = curr;
curr = curr->next;
}
}
//删除结点，释放空间
minpre ->next = minNode->next;
free(minNode) ;
}