13．已知非空线性链表的第一个结点的指针为head，请写一个算法，将该链表中数据域值最小的结点移动到链表的最前端。编写的函数具有如下原型：voidfunc(TLinkNode*head),其中链结点的结构如

Question

13．已知非空线性链表的第一个结点的指针为head，请写一个算法，将该链表中数据域值最小的结点移动到链表的最前端。编写的函数具有如下原型：void func(TLinkNode *head),其中链结点的结构如下：
struct TLinkNode
{
int data;
TLinkNode *next;
}
请完成该算法。

Answer 1

typedef struct TLinkNode
{
int data;
TLinkNode *next;
}LinkNode;
void func(TLinkNode * &head)
{
if(head == NULL)
return;
TLinkNode *min = head;//记录最小值节点
TLinkNode *node = head;//遍历过程中的当前节点
TLinkNode *pre;//遍历过程中当前节点的前一个节点
TLinkNode *beforeMin = head;//记录最小值节点的前一个节点
while(node)
{
pre = node;
node = node->next;
if(node != NULL && node->data < min->data)
{
beforeMin = pre;
min = node;
}
}
if(min->data == head->data)
return;
if(min->next == NULL)
{
beforeMin->next = NULL;
min->next = head;
head = min;
}
else
{
beforeMin->next = min->next;
min->next = head;
head = min;
}
}
以及测试过了，可以使用
测试代码如下：
TLinkNode *p1 = new LinkNode;
p1->data = 3;
p1->next = NULL;
TLinkNode *p2 = new LinkNode;
p2->data = 2;
p2->next = p1;
TLinkNode *p3 = new LinkNode;
p3->data = 1;
p3->next = p2;
func(p3);
TLinkNode *p = p3;
while(p)
{
cout << p->data << ' ';
p = p->next;
}
变换p1,p2,p3的值，运行结果均无误