有一个有序单链表（从小到大排序），表头指针为head，编写一个函数向该单链表中插入一个元素为x的结点，使插入后该链表仍然有序。
有一个有序单链表（从小到大排序），表头指针为head，编写一个函数向该单链表中插入一个元素为x的结点，使插入后该链表仍然有序。
输入长度n：5
输入数据：1 6 8 9 10
输入插入数据：7
输出：1 6 7 8 9 10
4 1 2 3 4 6
1 2 3 4 6
#include <iostream>
#define NULL 0
using namespace std;
struct student
{
int num;
student *next;
};
int n;
student *creat(int m)
{
student *head,*p1,*p2;
p1=p2=new student;
cin>>p1->num;
head=NULL;
n=0;
while(p1->num!=NULL)
{
n=n+1;
if(n==1)head=p1;
else p2->next=p1;
p2=p1;
p1=new student;
if(n==m)
{break;}
else
cin>>p1->num;
}
p2->next=NULL;
return(head);
}
void print(student *head)
{
student *p;
p=head;
if(head!=NULL)
do
{
cout<<p->num<<" ";
p=p->next;
}while(p!=NULL);
}
student *intset(student *head,student *stud)
{
student *p0,*p1,*p2;
p1=head;//使p1指向第一个结点
p0=stud;//p0指向要插入的数值
if(head==NULL)//原链表为空时
{
head=p0;
p0->next=NULL;
}
else
{
while((p0->num>p1->num)&&(p1->next!=NULL))
{
p2=p1;//p2指向刚才的结点
p1=p1->next;//p1指向下一结点
}
if(p0->num<=p1->num)
{
if(head==p1)//插入到第一个结点之前
head=p0;
else p2->next=p0;//将p0插入到结点之后
p0->next=p1;
}
else//插到最后一个结点之后
{
p1->next=p0;
p0->next=NULL;
}
}
return (head);
}
int main()
{
int m,num;
cin>>m;
student *head,*stud;
student *creat(int);
void print(student *);
student *intset(student *,student *);
head=creat(m);
stud=new student;//开辟新的空间
cin>>stud->num;
intset(head,stud);
print(head);
return 0;
}
原文：http://blog.csdn.net/u013629228/article/details/21867253