问题 B: 案例3-1.1：线性表元素的区间删除

题目描述

给定一个顺序存储的线性表，删除线性表中所有小于r且大于l的元素。删除后剩余元素保持顺序存储，相对位置不变。

输入格式

第一行元素个数n、区间l、r。1<=n<=1e6,0<=l<=r<=1e8.
第二行n个整数，对应顺序表的各元素。对于每个元素Ai满足0<=Ai<=1e8

输出格式

第一行输出删除后元素的个数
第二行输出删除后顺序表中的元素，没有元素直接换行

输入样例

10 0 4
4 -8 2 12 1 5 9 3 3 10

输出样例  

6
4 -8 12 5 9 10

代码展示 

 楼主一开始写成函数形式（但是超时了）

#include<iostream>
using namespace std;

struct Node{
	int data;
	Node* next;
};
typedef Node* List;

int InitList(List &list){
	list=new Node;
	list->next=NULL;
	return 0;
}
int DestroyList(List &list){
	List p1,p2;
	p1=list;p2=list;
	while(p1!=NULL){
		p1=p1->next;
		free(p2);
		p2=p1;
	}
	return 0;
}
int AddNode(List &list,int data){
	List head=list;
	List p1=head;
	List p2=new Node;
	p2->data=data;
	p2->next=NULL;
	if(head==NULL){
		head->next=p2;
	}
	else{
		while(p1->next!=NULL){
			p1=p1->next;
		}
		p1->next=p2;
	}
	return 0;
}
int SelectiveDelete(List &list,int l,int r){
	int count=0;
	List p1,p2;
	p1=list;
	while(p1->next!=NULL){
		if(p1->next->data > l && p1->next->data < r){
			p2=p1->next;
			p1->next=p2->next;
			free(p2);
			p2=p1;
			count++;
		}
		else{
			p1=p1->next;
		}
	}
	return count;
}

void PrintList(const List &list){
	Node *p=list->next;
	while(p!=NULL){
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
}

int main(){
	int n;
	int l,r;
	cin>>n>>l>>r;
	List list;
	InitList(list);//链表初始化
	for(int i=0;i<n;i++){
			int v;
			cin>>v;
			AddNode(list,v);
	}//填入链表数据
	int count;
	count=SelectiveDelete(list,l,r);
	cout<<n-count<<endl;
	PrintList(list);
	DestroyList(list);
	return 0;
}

为了解决超时问题，改进得到以下版本

#include<iostream>
using namespace std;

struct Node{
	int data;
	Node* next;
};
typedef Node* List;

// int InitList(List &list){
// 	list=new Node;
// 	list->next=NULL;
// 	return 0;
// }
int DestroyList(List &list){
	List p1,p2;
	p1=list;p2=list;
	while(p1!=NULL){
		p1=p1->next;
		free(p2);
		p2=p1;
	}
	return 0;
}
// int AddNode(List &list,int data){
// 	List head=list;
// 	List p1=head;
// 	List p2=new Node;
// 	p2->data=data;
// 	p2->next=NULL;
// 	if(head==NULL){
// 		head->next=p2;
// 	}
// 	else{
// 		while(p1->next!=NULL){
// 			p1=p1->next;
// 		}
// 		p1->next=p2;
// 	}
// 	return 0;
// }
int SelectiveDelete(List &list,int l,int r){
	int count=0;
	List p1,p2;
	p1=list;
	while(p1->next!=NULL){
		if(p1->next->data > l && p1->next->data < r){
			p2=p1->next;
			p1->next=p2->next;
			free(p2);
			p2=p1;
			count++;
		}
		else{
			p1=p1->next;
		}
	}
	return count;
}

void PrintList(const List &list){
	Node *p=list->next;
	while(p!=NULL){
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
}

int main(){
	//freopen("/config/workspace/test/test","r",stdin);
	int n;
	int l,r;
	cin>>n>>l>>r;
	List list;
	list=new Node;
	list->next=NULL;
	List p1,p2;
	p1=list;
	//InitList(list);//链表初始化
	for(int i=0;i<n;i++){
			p2=new Node;
			cin>>p2->data;
			p2->next=NULL;
			p1->next=p2;
			p1=p2;
			//AddNode(list,v);
	}//填入链表数据
	int count;
	count=SelectiveDelete(list,l,r);
	cout<<n-count<<endl;
	PrintList(list);
	DestroyList(list);
	return 0;
}