综合题

写一算法, 将带有头结点的非空单链表中数据域值最小的那个结点移到链表的最前面。 要求: 不得额外申请新的链结点。 函数原型如下:
void delinsert(LinkList &L);

【正确答案】

void delinsert(LinkList &L)
{
p=L->next; //p 是链表的工作指针
pre=L; //pre 指向链表中数据域最小值结点的前驱
q=p;
//q 指向数据域最小值结点, 初始假定是第一结点
while(p->next!=NULL)
{
if(p->next->data<q->data) //找到新的最小值结点
{ pre=p; q=p->next; }
p=p->next;
}
if(q!=L->next) //若最小值是第一元素结点, 则不需再操作
{
pre->next=q->next; //将最小值结点从链表上摘下
q->next=L->next; //将 q 结点插到链表最前面
L->next=q;
}
}

【答案解析】