已知两个链表 la和 lb，其元素值递增排序。编程将la和lb合并成一个递减有序（相同值元素只保留一个）的链表lc。（北方名校经典试题） 本题选做

#include <iostream>//compare.cpp
#include "Node.h"
#include "SimpleLinkList.h"
using namespace std;

template<class ElemType>
void oppositedSequence(SimpleLinkList<ElemType> &lc)
{
	int atemp;
	int btemp;
	int length=lc.Length();
	for(int i=1;i<=(int)(length/2);i++)
	{
		lc.GetElem(i,atemp);
		lc.GetElem(length-i+1,btemp);
		lc.SetElem(i,btemp);
		lc.SetElem(length-i+1,atemp);
	}
}

template<class ElemType>
void MergeList(SimpleLinkList<ElemType> &la,SimpleLinkList<ElemType> &lb,SimpleLinkList<ElemType> &lc)
{
	int aLength=la.Length(),bLength=lb.Length(),aPosition=1,bPosition=1;
	ElemType aItem,bItem,cItem;
	while(aPosition<=aLength&&bPosition<=bLength)
	{
		la.GetElem(aPosition,aItem);
		lb.GetElem(bPosition,bItem);
		
		if((!lc.Exist(aItem))&&(!lc.Exist(bItem)))
		{
			if(aItem<=bItem)
			{
				lc.Insert(lc.Length()+1,aItem);
				lc.Insert(lc.Length()+1,bItem);

			}
			else
			{
				lc.Insert(lc.Length()+1,bItem);
				lc.Insert(lc.Length()+1,aItem);
		
			}
		}else if(lc.Exist(aItem)&&lc.Exist(bItem))
		{

		}else if(lc.Exist(aItem))
		{

			lc.Insert(lc.Length()+1,bItem);

		}		
		else 
		{

			lc.Insert(lc.Length()+1,aItem);
		
		}
		aPosition++;
		bPosition++;	
		
			
	}
	while(aPosition<=aLength)
	{
		la.GetElem(aPosition,aItem);
		if(lc.Exist(aItem))
		{
			aPosition++;
			continue;
		}
		lc.Insert(lc.Length()+1,aItem);
		aPosition++;
	}
	while(bPosition<=bLength)
	{
		lb.GetElem(bPosition,bItem);
		if(lc.Exist(bItem))
		{
			bPosition++;
			continue;
		}
		lc.Insert(lc.Length()+1,bItem);
		bPosition++;
	}
	//逆序排列
	oppositedSequence(lc);
}
void main()
{
	SimpleLinkList<int> la,lb,lc;
	for(int i=1,k=2;i<3;i++,k++)//定义la和lb为递增排列的链表
	{
		la.Insert(i,i);
		lb.Insert(i,k);
	}
//	lb.Insert(3,5);
	la.Insert(3,7);
	MergeList(la,lb,lc);
	for(int j=1;j<=lc.Length();j++)
	{
		int cTemp;
		lc.GetElem(j,cTemp);
		cout<<cTemp<<" ";
	}
	cout<<endl;
	
}
#ifndef _NODE_H_//Node.h
#define _NODE_H_
#include <iostream>
using namespace std;

template<class ElemType>
struct Node
{
	ElemType data;
	Node<ElemType> *next;
	Node();
	Node(ElemType item,Node<ElemType> *link=NULL);
};

template<class ElemType>
Node<ElemType>::Node()
{
	next=NULL;
}

template<class ElemType>
Node<ElemType>::Node(ElemType item,Node<ElemType> *link)
{
	data=item;
	next=link;
}
#endif

#ifndef _SIMPLELINKLIST_H_//SimpleLinkList.h
#define _SIMPLELINKLIST_H_
#include "Node.h"
#include <iostream>
using namespace std;
enum StatusCode{SUCCESS,FAIL,UNDER_FLOW,RANGE_ERROR,DUPLICATE_ERROR,NOT_PRESENT,ENTRY_INSERTED,ENTRY_FOUND,VISITED,UNVISITED};
template<class ElemType>
class SimpleLinkList
{
protected:
	Node<ElemType> *head;
	Node<ElemType> *GetElemPtr(int position)const;
	void Init();
public:
	
	SimpleLinkList();
	virtual ~SimpleLinkList();
	int Length()const;
	bool Empty()const;
	void Clear();

	StatusCode GetElem(int position,ElemType &e)const;
	StatusCode SetElem(int position,ElemType e);
	StatusCode Delete(int position,ElemType &e);
	StatusCode Insert(int position,ElemType e);

	SimpleLinkList(const SimpleLinkList<ElemType> &copy);
	SimpleLinkList<ElemType> operator = (const SimpleLinkList<ElemType> &copy);
	bool Exist(ElemType &e);
};

template<class ElemType>
bool SimpleLinkList<ElemType>::Exist(ElemType &e)
{
	for(Node<ElemType>* tmpPtr=head;tmpPtr!=NULL;tmpPtr=tmpPtr->next)
	{
		if(tmpPtr->data==e)
			return true;
	}
	return false;
		
}
template<class ElemType>
Node<ElemType> *SimpleLinkList<ElemType>::GetElemPtr(int position)const
{
	Node<ElemType> *tmpPtr=head;
	int curPosition=0;
	while(tmpPtr!=NULL&&curPosition<position)
	{
		tmpPtr=tmpPtr->next;
		curPosition++;
	}
	if(tmpPtr!=NULL&&curPosition==position)
		return tmpPtr;
	else
		return NULL;
		
}
//实现
template<class ElemType>
SimpleLinkList<ElemType>::SimpleLinkList()
{
	Init();
}

template<class ElemType>
void SimpleLinkList<ElemType>::Init()
{
	head=new Node<ElemType>;
}

template<class ElemType>
SimpleLinkList<ElemType>::~SimpleLinkList()
{
	Clear();
	delete head;
}

template<class ElemType>
int SimpleLinkList<ElemType>::Length()const
{
	int count=0;
	for(Node<ElemType> *tmpPtr=head->next;tmpPtr!=NULL;tmpPtr=tmpPtr->next)
		count++;
	return count;
}

template<class ElemType>
void SimpleLinkList<ElemType>::Clear()
{
	ElemType tmpElem;
	while(Length()>0)
		Delete(1,tmpElem);
}

template<class ElemType>
bool SimpleLinkList<ElemType>::Empty()const
{
	return head->next==NULL;
}

template<class ElemType>
StatusCode SimpleLinkList<ElemType>::GetElem(int position,ElemType &e)const
{
	if(position<1||position>Length())
		return RANGE_ERROR;
	else
	{
		e=((GetElemPtr(position))->data);
		return ENTRY_FOUND;
	}
}

template<class ElemType>
StatusCode SimpleLinkList<ElemType>::SetElem(int position,ElemType e)
{
	if(position<1||position>Length())
		return RANGE_ERROR;
	else
	{
		(GetElemPtr(position))->data=e;
		return SUCCESS;
	}
}

template<class ElemType>
StatusCode SimpleLinkList<ElemType>::Insert(int position,ElemType e)
{
	if(position<1||position>Length()+1)
		return RANGE_ERROR;
	else
	{
		Node<ElemType> *tmpPtr=GetElemPtr(position-1);
		Node<ElemType> *s=new Node<ElemType>(e,tmpPtr->next);
		tmpPtr->next=s;
		return SUCCESS;
	}

}

template<class ElemType>
StatusCode SimpleLinkList<ElemType>::Delete(int position,ElemType &e)
{
	if(position<1||position>Length())
		return RANGE_ERROR;
	else
	{
		Node<ElemType> *tmpPtr=GetElemPtr(position-1);
		Node<ElemType> *deletePtr=tmpPtr->next;
		tmpPtr->next=deletePtr->next;
		e=deletePtr->data;
		delete deletePtr;
		return SUCCESS;
	}
}

template<class ElemType>
SimpleLinkList<ElemType>::SimpleLinkList(const SimpleLinkList<ElemType> &e)
{
	for(int i=1;i<=e.Length();i++)
	{
		ElemType eElem;
		e.GetElem(i,eElem);
		Insert(i,eElem);
	}
}

template<class ElemType>
SimpleLinkList<ElemType> SimpleLinkList<ElemType>::operator = (const SimpleLinkList<ElemType> &e)
{
	SimpleLinkList<ElemType> *a=new SimpleLinkList<ElemType>(e);
	return a;
}
#endif