#include<iostream.h>
//單鏈表節點類
template<class ElemType>class List;// 單鏈表類的向前說明
template<class ElemType>class ListItr;// 單鏈表迭代器類的向前說明
template<class ElemType>class ListNode{
	friend class List<ElemType>;// 單鏈表類為其友元類, 便于訪問結點類中的私有成員
	friend class ListItr<ElemType>; //單鏈表迭代器類為其友元類, 便于訪問結點類中的私有成員
	private:
		ListNode<ElemType> *Next; // 指向下一個結點的指針。
		ElemType Element;// 結點數據。
	public:
		ListNode(const ElemType &E,ListNode<ElemType> *N=NULL)
			:Element(E),Next(N){}// 構造函數
		ListNode():Next(NULL){}// 析構函數
		~ListNode(){}
};
//單鏈表類
template<class ElemType>class List{
	friend class ListItr<ElemType>;    // 單鏈表迭代器類為其友元類
	private:
		ListNode<ElemType> *head;// 指向頭結點的指針
	public:
		List(){head=new ListNode<ElemType>();}
		~List(){MakeEmpty();delete head;}// 析構函數
		const List &operator = (const List&R);// 完成復制功能。
		int IsEmpty()const{return head->Next==NULL;}
		int IsFull()const {return 0;}
		void MakeEmpty();
	    List& operator ^ (List<ElemType> &);//求兩個的交集
};
template<class ElemType>
const List<ElemType>&List<ElemType>::operator = (const List<ElemType>&R){
	if(this==&R) return *this;      // 同一單鏈表，不必賦值。
	MakeEmpty();	// 清空單鏈表。
	ListItr<ElemType>Itr(*this);
	for(ListItr<ElemType>Ritr(R);+Ritr;Ritr++) Itr.Insert(Ritr());
	return *this;// 根據單鏈表R 的結點數據值，創建新結點，并插入到當前鏈表
}
template<class ElemType>
List<ElemType> & List<ElemType>::operator ^ (List<ElemType> &l)//求交集
{
	ListItr<ElemType> listitr1(*this),listitr2(l);
	ElemType a,b;
	for(;+listitr1&&+listitr2;){
		a=listitr1();b=listitr2();
		if(a>b){				//a大時		
			listitr2++;
			listitr2.Remove(b);
		}
		else 
			if(a<b){
//               listitr1++;
			   listitr1.Remove(a);   //a小時

		}
		else{		           //相等時
			listitr1++;
			listitr2++;
		}
	}
	for(;+listitr1;){//a為最后一個數據,而b都比它小時
		a=listitr1();
        listitr1++;
		listitr1.Remove(a);
	}
    return *this;
}

template<class ElemType>
void List<ElemType>::MakeEmpty(){
	ListNode<ElemType> *Ptr;
	ListNode<ElemType> *NextNode;
	for(Ptr=head->Next;Ptr!=NULL;Ptr=NextNode)
	{
		NextNode=Ptr->Next;
		delete Ptr;
	}
	head->Next=NULL;
}

template<class ElemType>
ostream &operator<<(ostream & Out,const List<ElemType> &L){
	if(L.IsEmpty()) Out<<"Empty List!";
	else for(ListItr<ElemType>Itr(L);+Itr;++Itr) Out<<Itr()<<endl;
	return Out;
}
template<class ElemType>
istream &operator>>(istream & is, List<ElemType> &L)
{
	ElemType a;
	ListItr<ElemType> Itr(L);
    while(is>>a,a!=-1) Itr.Insert(a);
	return is;
}
template<class ElemType>class ListItr{
private:
	ListNode<ElemType> * const head;// 指向頭結點的常指針
	ListNode<ElemType> * Current; // 指向當前結點的指針
public:
	ListItr(const List<ElemType>&L):head(L.head)
	{Current=L.IsEmpty()?head:head->Next;}
	~ListItr(){} // 析構函數
	int Find(const ElemType &x);      // 查找值為x的結點，查找成功則使其成為當前結點，并返回True
	int IsFound(const ElemType &x) const;// 查找值為x的結點，查找成功返回True，否則返回False;不改變指針Current的值
	void Insert(const ElemType &x);  // 插入成功，新結點成為當前結點
	int Remove(const ElemType &x);  // 刪除值為x的結點的操作
	int operator+()const
	{return Current && Current!=head;}  //當前結點非空則返回Ture
	const ElemType& operator()()const;  //取當前結點的數據值
	void operator++();   	// 使當前結點的直接后繼結點成為當前結點 前綴++運算符
    void operator++(int){operator++();}  // 將后綴運算符++定義為前綴++運算符
	void Zeroth(){Current=head;}// 當前指針指向頭結點
	void First();   // 當前指針指向首結點
	const ListItr &operator = (const ListItr &);// 賦值運算符
};
template<class ElemType>
void ListItr<ElemType>::Insert(const ElemType&x){
	ListNode<ElemType> *p;
	p=new ListNode<ElemType>(x,Current->Next);
	Current=Current->Next=p;
}
template<class ElemType>
int ListItr<ElemType>::Find(const ElemType &x){
	ListNode<ElemType> * Ptr=head->Next;
    while(Ptr!=NULL&&!(Ptr->Element==x)) Ptr=Ptr->Next;
	if(Ptr==NULL)return 0;
	Current=Ptr;
	return 1;
}
template<class ElemType>
int ListItr<ElemType>::IsFound(const ElemType &x) const{
	ListNode<ElemType> *Ptr=head->Next;
	while(Ptr!=NULL&&!(ptr->Element==x)) Ptr=Ptr->Next;
	return Ptr!=NULL;
}
template<class ElemType>
int ListItr<ElemType>::Remove(const ElemType&x){
    ListNode<ElemType>*Ptr=head;
    while(Ptr->Next!=NULL&&!(Ptr->Next->Element==x))
		Ptr=Ptr->Next;
	if(Ptr->Next==NULL)
		return 0;
	ListNode<ElemType> *p=Ptr->Next;
	Ptr->Next=Ptr->Next->Next;
	delete p;
	return 1;
}
template<class ElemType>
const ElemType &ListItr<ElemType>::operator ()()const{
	return Current->Element;
}
template<class ElemType>
void ListItr<ElemType>::operator ++ (){
	Current=Current->Next;
}
template<class ElemType>
const ListItr<ElemType>&ListItr<ElemType>::operator = (const ListItr<ElemType>&R){
	if(this==&R) return *this;
	Current=R.Current;
	return *this;
}
template<class ElemType>
void ListItr<ElemType>::First(){
	Current=head->Next;
}

int main()
{
	List<int> a,b;
	cout<<"Input two lists and -1 to stop:";
	cin>>a;
	cin>>b;
	cout<<"The same:";
	cout<<(a^b);
	return 0;
}