数据结构：在单链表中删除mink～maxk之间的元素

在单链表中删除mink～maxk之间的元素

前言

用于个人学习过程记录

题目

输入若干个值不超过1000的整数，建立递增有序的单链表，设计一个高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），mink和maxk可以与表中的元素相同，也可以不同。

测试数据不包含下面两种特殊情况： （1）mink大于最后一个数； （2）maxk小于第一个数。

输入格式:
首先输入一个整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据首先在第一行上输入数据个数n及n个递增有序的整数，存储在带头结点的单链表中；然后在下一行中输入整数mink、maxk（mink<maxk），表示要删除表中所有值大于mink且小于maxk的元素。

输出格式:
对于每组测试，输出删除表中所有值大于mink且小于maxk的元素后单链表中的元素，每两个元素之间留一个空格。

输入样例:

1
9 8 125 251 351 467 492 508 731 742
100 300

输出样例:

8 351 467 492 508 731 742

代码

#include<iostream>
using namespace std;
struct LNode{
	int data;
	LNode *next;
};
struct LinkList{
	LNode *head;
	void Init();
	void create(int n);
	void traverse();
};
void LinkList::Init(){
	head=new LNode;
	head->next=NULL;
}
void LinkList::create(int n){
	Init();
	LNode *p=head;
	while(n--){
		LNode *q=new LNode;
		cin>>q->data;
		q->next=p->next;
		p->next=q;
		p=q;
	}
}
void LinkList::traverse(){
	LNode *p= head->next;
	while(p){
		if(p!=head->next) cout<<" ";
		cout<<p->data;
		p=p->next;
	}
	cout<<endl;
}
void deletelist(LinkList La,int mink,int maxk){
	LNode *p =La.head;
	while(p){
		LNode *q=p,*r=p->next;
		while(r){
			if(r->data > mink && r->data < maxk){
				LNode *s=r;
				q->next=r->next;
				r=r->next;
				delete s;
			}
			else{
				q=r;
				r=r->next;
			}
		}	
		p=p->next;
	}
}
int main(){
	int T;	
	cin>>T;
	while(T--){
		int n;
		cin>>n;
		LinkList a;
		a.create(n);
		int mink,maxk;
		cin>>mink>>maxk;
		deletelist(a,mink,maxk);
		a.traverse();
	}
}