【答案解析】算法设计的基本思路是：按照链表插入排序的思想，将sort链初始化为只有一个结点(首元结点)的有序单链表，然后扫描link链的每个结点，一边扫描一边将结点按其值插入到sort链中。算法实现如下：
Typedef struct node{ //链表结点类型定义
int data; //数据域
struct node*link; //原有单链表的链接指针
struct node*sort; //将生产的有序单链表的链接指针
}DLNode;
Typedef DLNode*DList; //链表类型定义
Void sortList(DList list){
//利用链表list的sort域建立按照结点数据值升序链接的单链表
List-＞sort=list-＞link:list-＞sort-＞NULL;
DLNode*p,*prep,*s=list-＞link-＞link;
while(s!=NULL){
p=list-＞sort;prep=list;
while(p!=NULL&&P-＞data＜s-＞data)
//寻找sort链中插入位置
{prep=p;p=p-＞soft;}
prep-＞sort=s;s-＞sort=p; //链入sort链
s=s-＞link; //处理link链的下一结点
}
}
此算法有一个嵌套的循环。其中，外层循环执行n-1次，而内层循环的执行次数取决于数据值。最好情况是原链表中所有结点的数据值都按降序排列，每次插入时仅比较1次；最坏情况是原链表中所有结点的数据值都按升序排列，这样在插入第i(2≤i≤n)个结点时需要比较i-1次。所以，最好情况下算法的数据比较次数为O(n)，最坏情况下算法的数据比较次数为O(n ² )。
算法的数据移动次数为0，因为链表插入只需修改结点指针，不需移动元素。