链表的记录进行就地排序

【题目】设一单向链表的头指针为head,链表的记录中包含着整数类型的key域,试设计算法,
将此链表的记录按照key递增的次序进行就地排序.（不允许使用数组做辅助存储）

【来源】中科院计算机技术研究所1999年第五（1）题 （10’）
华中理工大学2000年第八（2）题 （13’）

【解答】
typedef struct CircleList{ // 定义循环链表
int key;
struct CircleList *next;
}*listnode;

ListSort(listnode head)
{
int k,min,i,j;
listnode p,q,t;
p=head->next;
while(p->next!=head->next){p=p->next;k+=1;} // 统计链表中元素个数，保存在 K 中
p=head;j=1;
for(i=1;iwhile(j<=i){p=p->next;j++;} // 找应填入当前最小元素的位置，该位置保存在 q 中
min=p->key;q=p; // 将当前位置元素的值设为初始最小值
while(p->next!=head->next){
if(min>p->key){min=p->key;t=p;} // 找当前最小元素，并保存在 t 所指位置中
p=p->next;
}
t->key=q->key;q->key=min;j=1; // 交换 q 位置元素和最小元素的值
}
}

【分析】本题不需要修改链表中的各个指针。