花了38分钟才写出来，多练多练！！！ 总结：用两个结点夹逼出待插入节点的位置 :定位好插入点后，当 p 为“NULL”时，插入点是链表头部；当 q 为“NULL”时，插入点是链表尾部；否则，插入点为 p 和 q 指向的两个结点之间。
#include <iostream> using namespace std; // 定义结点结构 struct node { int data; // 数据域 node * next; // 指针域,指向下一个结点 }; // 函数insertSort：链表排序插入 // 参数：h-链表头指针，t-指向要插入的结点 // 返回值：插入结点后链表的首结点地址 node * insertSort(node *h, node *t); // 函数insertHead：链表头部插入 // 参数：h-链表头指针，t-指向要插入的结点 // 返回值：插入结点后链表的首结点地址 node * insertHead(node *h, node *t); // 函数printList：输出链表，每个数据之间用一个空格隔开 // 参数：h-链表头指针 void printList(node *h); // 函数insertTail：链表尾部插入 // 参数：h-链表头指针，t-指向要插入的结点 // 返回值：插入结点后链表的首结点地址 node *insertTail(node *h, node *t); // 函数delList：删除链表，释放空间 // 参数：h-链表头指针 void delList(node *h); node * insertSort(node *h, node *t) { // 请在此添加代码，补全函数insertSort /********** Begin *********/ if(h == NULL){ t->next = NULL; return t; } node* q=h; node* p=NULL; while(q){ if(q->data > t->data ){ //找到插点 if(p == NULL){ t->next = q; return t; //插入点是链表头部 } p->next = t; t->next = q; return h; }else{ p = q; q = q->next; } } if(q== NULL){ p->next = t; } return h; /********** End **********/ } int main() { int n,i; node *t; node *head=NULL; //头指针为NULL，表示线性表为空，结点数为0 //输入结点数 cin>>n; for(i=0;i<n;i++) { //为新节点动态分配空间 t = new node; cin>>t->data; //输入结点数据 t->next=NULL; //结点指针域值为空 //调用函数插入结点，按data从小到大排序插入 head = insertSort(head, t); } //输出链表 printList(head); //删除结点，释放空间 delList(head); return 0; } //函数delList：删除链表，释放空间 //参数：h-链表头指针 void delList(node *h) { node *p=h; //指针p指向头结点，第一个要删除的结点 while(p) //这个结点是存在的 { h = h->next; //头指针h指向下一个结点（下一个结点的地址存在当前结点的指针域中，即h->next中 delete p; //删除p指向的结点 p = h; //p指向当前的头结点，即下一个要删除的结点 } } //函数printList：输出链表，每个数据之间用一个空格隔开 //参数：h-链表头指针 void printList(node *h) { cout<<"List:"; while(h) {//h为真，即h指向的结点存在，则输出该结点的数据 cout<<" "<<h->data; //输出结点数据 h=h->next; //将该结点的指针域赋值给h，h就指向了下一个结点 } cout<<endl; //输出换行符 } //函数insertTail：链表尾部插入 //参数：h-链表头指针，t-指向要插入的结点 //返回值：插入结点后链表的首结点地址 node *insertTail(node *h, node *t) { if(h==NULL) //空链表单独处理 { t->next=NULL; //链表尾指针置为NULL return t; //返回第一个结点的地址（即链表头指针） } //非空链表的情况 node *p=h; //让p指向最后一个结点 while(p->next) p=p->next; p->next = t; //让最后一个结点的指针域指向结点t t->next=NULL; //链表尾指针置为NULL return h; //返回第一个结点的地址（即链表头指针） } //函数insertHead：链表头部插入 //参数：h-链表头指针，t-指向要插入的结点 //返回值：插入结点后链表的首结点地址 node * insertHead(node *h, node *t) { t->next=h; return t; }