直接插入排序法的基本思想是：对于参加排序的原始序列(k0,1，k0,2，…，k0,n)，第i趟排序将序列的第i+1个元素插入到大小为i、且已经按值有序的子序列(ki-1,1，ki-1,2，…，ki-1,i)的合适位置，得到一个大小为i+l、且仍然按值有序的子序列(ki,1，ki,2，…，ki,i+1)，其中，ki,j表示第i趟排序结束时序列的第j个元素，1≤i≤n-1，1≤j≤n。已知一个整数序列的各元素依次存放于无头结点的非循环双向链表的各链结点。链结点构造为：第一个链结点的指针为list，请写出直接插入排序算法。算法中不得使用任何新的链结点空间，也不允许出现修改链结点数据域内容的动作。
根据设计思想，采用C或C++或JAVA语言表述算法，关键之处给出注释。
参考答案：算法的实现过程如下：
void insertion(LinkList * list){
LinkNode *p, *q;
int min; //min用来记录链表中的最小值
p=list;
if(p=null) return; //空表的情况
q=list-＞next;
if(q==null) return; //只有一个结点的情况
if(q-＞data＜min){ //结点个数多于一个时, 特殊处理第一个结点
min=q-＞data;
p-＞next=q-＞next; //插入排序修改指针
q-＞next-＞prior=p;
q-＞next=p;
list=q;
}//第一个结点的处理
p=list;
q=p-＞next;
min=p-＞data;
while(q!=null){ //非首元素的链结点的处理
if(q-＞data＜min){
min=q-＞data;
p-＞next=q-＞next;
q-＞next-＞prior=p;
q-＞next=p;
q=p-＞next;
}
}