数据结构与算法——递增链表的插入

题目描述
给定一个递增整数序列和某个整数M，构造出此递增序列对应的链表，并创建以M为值的新结点插入到链表中，使其结果序列依然保持递增顺序。

输入
每个输入包含一个测试用例，第1行包含原序列长度N（任意long int范围内的正整数）与待插入的整数M；第2行包含N个递增的整数代表原递增数列。

输出
根据此递增数列，构造出此递增链表，然后将M插入到链表中，输出插入后的链表对应的数列。数字间隔一个空格，但末尾不能有空格。

样例输入
6 2
-10 -3 1 5 9 30

样例输出
-10 -3 1 2 5 9 30

本题很忌讳使用两个指针同时指向同一动态内存的做法，如下：

void InsNode(LinkList PHead,DataType data)
{
	Node *p;
	Node *s;
	Node *q;
	p=PHead;
	q=PHead;    //此处p和q同时指向链表头结点，从思维上来说感觉没问题 
	p=p->Next;  //这样很容易产生误导，实际上这样做会出现一个严重问题
	while(p->Next!=NULL&&p->Data<data) 
	{       //两个指针变量如果指向同一动态内存，一个指针结束生命期释放内存              
		p=p->Next;//另一指针所指地址虽被释放，但该指针不等于NULL而是随机值
		q = q->Next;//此举十分容易引发野指针，导致内存破坏
	}
	if (p->Data > data)
	{
			s=(Node*)malloc(sizeof(Node));
			s->Data=data;
			s->Next=q->Next;
			q->Next=s;
	}
	else
	{
		s = (Node*)malloc(sizeof(Node));
		s->Data = data;
		p->Next = s;
		s->Next = NULL;
	}
}

具体代码如下：

#include <stdio.h>
#include<stdlib.h>
typedef struct Node{
	int data;
	struct Node *next;
}Node,*LinkList;
//链表初始化
void InitList(LinkList *P){
	*P = (LinkList)malloc(sizeof(Node));
	if(*P==NULL){
		return; 
	}
	(*P)->next=NULL;	
} 
//链表插入（尾插法）
void CFromBack(LinkList P,int n){
	int data,i;
	Node *p,*s;
	s=P;
	for(i=0;i<n;i++){
		scanf("%d",&data);
		p=(LinkList)malloc(sizeof(Node));
		p->data=data;
		p->next=s->next;
		s->next=p;
		s=p;
	}
} 
//在链表中插入数据
LinkList function(LinkList P,int m){
	Node *p,*s;
	p=P;
	s=(LinkList)malloc(sizeof(Node));
	s->data=m;
	s->next=NULL;
	while(P->next!=NULL&&P->next->data<m){   //寻找插入位置
		P=P->next;
	}
	s->next=P->next;
	P->next=s;
	return p;
}
//打印链表
void PrintList(LinkList P){
	Node *p;
	p=P;
	while(p->next!=NULL){
		p=p->next;
		printf("%d ",p->data);
	}
}

int main(){
	int M,N;
	LinkList L;
	InitList(&L);
	scanf("%d %d",&N,&M);
	CFromBack(L,N);
	L=function(L,M);
	PrintList(L);
}