## 问题描述 > 有一个带头结点的单链表对其排序，使之递增有序。 ## 算法思想 > 本题是仅仅要求完成排序，因此我们很容易的想到使用插入排序算法完成单链表的排序。 首先将单链表的头结点拆下，用指针p指向剩余的不带头结点的那部分链表的的第一个结点，指针q指向指针p指向的结点的下一个结点。然后将指针p指向的结点摘下，使用指针pre对带有头结点的那部分链表进行遍历，如果指针pre所指结点的下一个结点的数据域值比指针p所指结点的数据域的值大，则将指针p所指结点插入到指针pre所指结点的后面，这样便完成了一次排序过程。重新让指针p指向不带头节点的那部分链表的第一个结点，指针q指向指针p所指结点的下一个结点，重新开始一次排序。 如图所示：  ## 算法描述 ~~~ void Sort(LNode *head) { LNode *pre=head; LNode *p=pre->next; LNode *q=p->next; p->next=NULL; p=q; while(q){ q=p->next; pre=head; while(pre->next!=NULL&&pre->next->data<p->data){ pre=pre->next; } p->next=pre->next; pre->next=p; p=q; } } ~~~ 具体代码见附件 ## 附件 ~~~ #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; LinkList CreatList(LNode*); void Sort(LNode*); void Print(LNode*); int main(int argc, char* argv[]) { LNode *head; head=(LNode*)malloc(sizeof(LNode)); head->next=NULL; head=CreatList(head); Print(head); Sort(head); Print(head); return 0; } //头插法创建单链表 LinkList CreatList(LNode* head) { LNode *L; ElemType x; scanf("%d",&x); while(x!=999){ L=(LNode*)malloc(sizeof(LNode)); L->data=x; L->next=head->next; head->next=L; scanf("%d",&x); } return head; } //直接插入排序 void Sort(LNode *head) { LNode *pre=head; LNode *p=pre->next; LNode *q=p->next; p->next=NULL; p=q; while(q){ q=p->next; pre=head; while(pre->next!=NULL&&pre->next->data<p->data){ pre=pre->next; } p->next=pre->next; pre->next=p; p=q; } } //打印全部结点 void Print(LNode *head) { LNode *p=head->next; while(p){ printf("%4d",p->data); p=p->next; } printf("\n"); } ~~~