在有序链表插入一个元素

struct node{
	int data;
	struct node *next;
};//创建结构体 表示链表的节点类型 

主函数

struct node *head,*p,*q,*t;
	int n,a;
	cin>>n;
	head=NULL;//头指针初始化为空 
	for(int i=0;i<n;i++){
		cin>>a;//input 
		
		p=(struct node*)malloc(sizeof(struct node));//动态申请一个空间 用来存放一个节点 
		//并将临时节点p指向这块内存
		 
		p->data=a;//将a存储在这个节点的data域中 
		p->next=NULL;//将当前节点的后继指针指向空 
		if(head==NULL){
			head=p;//如果是是第一个节点 将头指针指向这个节点 
		}
		else{ 
			q->next=p;//如果不是第一个节点 将上一节点的后继指针指向当前的节点 
		}

		q=p;//更新上一节点 
		p=NULL;//将临时节点p变为空指针 
	}

插入

注意:

如果这个链表很长，且每个节点的值相同
再插一个相同的值进去会遍历整个链表然后插入到链表尾部 浪费了时间
将大于号改为大于等于

   cin>>a; //输入插入的数字 
t=head;//从头指针开始遍历 
while(t!=NULL){
	if(t->next==NULL||t->next->data>=a){//如果是在最后一个数字 下一节点指向空或者下一集结点的data域的大小比新插入的数字要大 
		p=(struct node*)malloc(sizeof(struct node));//动态申请一个空间 存放新增节点 
		p->data=a;//将新节点的data域更新为插入的值 
		p->next=t->next;//将新节点的下一节点于t节点的下一节点相连 
		t->next=p;//将t节点的下一节点更新为新节点p 
		p=NULL;//初始化临时指针p 
		break;
	}
	t=t->next;//向下一节点遍历 
}

输出

   t=head;
while(t!=NULL){
	cout<<t->data<<" ";//从头节点开始输出 
	t=t->next;//向下一节点遍历 
}
free(t);//清空t指针指向的内存 
t=NULL;//t初始化为空指针