#include <iostream>
typedef int ElemType;

using namespace std;

class LNode
{
public:
	ElemType data;
	LNode  *next;
};

class linklist
{
public:
	LNode *list;
private:
	int size;
public:
	linklist()
	{
		list=NULL;
		size=0;
	}
   int CreateList(ElemType data)
	{
		LNode *node=new LNode();
		node->data=data;
		node->next=NULL;
		if(list==NULL)
		{
			list=node;
		}
		else
		{
			LNode *p;
			p=list;
			while(p->next!=NULL)
			{
				p=p->next;
			}
			p->next=node;			
		}
		size++;
		return size;
	}
   bool ListDelete_data(LNode *List,ElemType &data)
	{
		LNode *p,*q;
		p=list;
		q=list;
		int x=size;
		while((p->next)!=NULL)
		{
			if(p->data!=data)
			{
				q=p;
				p=q->next;
			}
			else
			{
				q->next=p->next;
				free(p);
				size--;
				break;
			}
		}
    	if(x==size)
			return false;
		else
			return true;
	}
   bool ListDelete_dataes(LNode *list,int i,int j)
   {
	   LNode *p,*q;
	   p=list;
	   int x=size;
	   if(i+j>size)
	   {
		   cout<<"輸入的長度超過鏈表的結點數!"<<endl;
	   }
	   else
	   {
		   for(int m=1;m<i;m++)
		   {
			   p=p->next;
			   q=p;
		   }
		   for(int k=0;k<j;k++)
		   {
			   p=q->next;
			   q->next=p->next;
			   free(p);
			   p=q;
			   size--;
		   }
	   }
	   if(x==size)
		   return false;
	   else
		   return true;

   }
   bool listDelete_overturn(LNode *list)
   {
	   LNode *p,*q,*m,*n;
	   p=list;
	   m=p;
	   while(p->next!=NULL)
	   {
		   q=p;
		   p=p->next;
	   }
	   q->next=NULL;
	   n=p;
	   list=p;
	   p->next=m;
	   while(m->next!=NULL)
	   {
		   while(p->next!=NULL)
		   {
			   q=p;
			   p=p->next;
		   }
		   q->next=NULL;
		   n->next=p;
		   n=p;
		   p->next=m;
	   }
	   p=list;
	   cout<<"逆轉后鏈表為:";
	   while(p!=NULL)
	   {		   
		   int x=p->data;
		   cout<<x<<"  ";
		   p=p->next;		   
	   }
      return true;
   }

   bool ordertraverse(LNode *llist)
   {
	   LNode *p;
	   p=llist;
	   while(p!=NULL)
	   {
		   int x=p->data;
		   cout<<x<<"  ";
		   p=p->next;
	   }
	   return true;
   }
  
};

void main()
{
	int n,i,j,z,k=0;
	cout<<"輸入結點個數n:";
	cin>>n;
	ElemType x,data;
	linklist *newlist=new linklist();
	cout<<"輸入每個結點數據:"<<endl;
	for(int a=0;a<n;a++)
	{
		cin>>x;
		newlist->CreateList(x);
	}
	while(k!=1)
	{
		cout<<"輸入1,2,3,4 選擇你要的功能:"<<endl;
		cout<<"(1)   逆轉該線性鏈表。"<<endl;
		cout<<"(2)   刪除線性鏈表中從左往右第一個數據為data的鏈結點。"<<endl;
		cout<<"(3)   刪除從第I個鏈結點開始的連續k個結點。"<<endl;
		cout<<"(4)   退出程序。"<<endl;
		cin>>z;
    	switch(z)
		{
		case 1:
			if(newlist->listDelete_overturn(newlist->list)==true)
			{
				cout<<"成功逆轉鏈表!"<<endl;
			}
			else
			{
				cout<<"刪除失敗!"<<endl;
			}
			break;
		case 2:
			cout<<"請輸入你要刪除的結點數據:";
			cin>>data;
			if(newlist->ListDelete_data(newlist->list,data)==true)
			{
				cout<<"刪除成功!"<<endl;
				cout<<"刪除后的鏈表數據為:";
				newlist->ordertraverse(newlist->list);
			}
			else
			{
				cout<<"不存在該數據!請確認后重新輸入!"<<endl;
			}
			break;
		case 3:
			cout<<"輸入你要從第幾個結點開始刪除:";
			cin>>i;
			cout<<"輸入要從該結點刪除之后的幾個結點元素:";
			cin>>j;
			if(newlist->ListDelete_dataes(newlist->list,i,j)==true)
			{
				cout<<"刪除成功!"<<endl;
				cout<<"刪除后的鏈表數據為:";
				newlist->ordertraverse(newlist->list);
			}
			else
			{
				cout<<"刪除失敗!"<<endl;
			}
			break;
		case 4:
			k=1;
			break;
		default:
			break;
		}
	}
}