[数据结构与算法]已知带头结点的动态单链表L中的结点是按整数值递增排列的，试写一算法将值x为的结点插入到表L中，使L仍然有序。

创建链表，main函数中通过while循环找出该插入的位置，插入。应注意L头节点位置的变化，利用一个ptr来记录L的头节点。

/*已知带头结点的动态单链表L中的结点是按整数值递增排列的，试写一算法将值x为的结点插入到表L

中，使L仍然有序。*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <math.h>

#define OK 1;

typedef int status;
typedef int ElemType;
/*链表的定义*/
typedef struct Node
{
	ElemType data;
	struct Node *next;
}LNode,*LinkList;

status InitList(LinkList &L)
{
	L=(LinkList)malloc(sizeof(struct Node));
	if(!L)
		exit(0);
	L->next =NULL;
	return OK;	
}

/*Insert函数将一个数值插入到链表当中，也可以用来链表的数值初始化*/
/*将num插入到第i个位置中*/
void InsertList(LinkList &L,int i,ElemType num)
{
	LinkList p=L;
	LinkList s;		/*把s设置为新节点*/
	int j=0;
	
	while(p&&j<i-1)/*让P指向第i-1个节点*/
	{
		p=p->next ;
		j++;
	}
	s=(LinkList)malloc(sizeof(struct Node));/*为新节点s分配空间*/
	s->data =num;
	s->next =p->next ;
	p->next =s;
	
}
int main(void)
{
	LinkList L,ptr;/*必须设置一个ptr，用以记录l的头节点，不然会像我一样调试半天*/
	int len;				/*自己输入链表长度*/
	int num,num2;			/*num2为要插入数字的值*/
	int i;
	InitList(L);			/*初始化链表*/
	ptr=L;					/*将l的head节点赋给ptr，记录头节点*/
	printf("请输入您要输入的数字的个数：");
	scanf("%d",&len);
	
	for(i=1;i<=len;i++)		/*输入链表的值*/
	{
		scanf("%d",&num);
		InsertList(L,i,num);
	}
	i=1;			/*将i置为1*/
	printf("请输入您想插入的数字：");
	scanf("%d",&num2); 
	while(L->next !=NULL)/*找到num2该插入的位置，并插入*/
	{
		L=L->next;
		if(num2<L->data )
		{
			L=ptr;		/*使l返回头节点*/
			InsertList(L,i,num2);
			break;
		}
		i++;
	}
	
	while(ptr->next !=NULL)
	{
		ptr=ptr->next;
		printf("%d\t",ptr->data );	
	}
	return 0;
	 
}